Dijkstra算法最短路径树重建复杂度为何是O(n+m)而非O(n*m)

嵌套循环的时间复杂度不能直接默认按两层循环的最大次数相乘计算，核心要看内层循环的实际总执行次数，这段代码的复杂度计算逻辑非常直接：

• 外层循环遍历所有顶点，总执行次数等于顶点数n，这部分开销为O(n)
• 内层循环对每个顶点v，仅遍历v自己的入边，而非全图所有m条边。对任意有m条边的图，所有顶点的入边数量总和恰好等于m（无向图中所有顶点邻接边总和为2m，量级仍为O(m)），也就是说所有内层循环的总执行次数加起来刚好是O(m)

两部分开销相加，总时间复杂度自然是O(n+m)，和DFS、BFS遍历图的时间复杂度逻辑完全一致。

你误判为O(nm)的核心原因，是默认内层循环每次都会遍历全量m条边——如果代码里内层是遍历全图所有边找指向v的边，那确实是O(nm)，但这里用的是邻接表存储的入边枚举接口g.incident_edges(v, False)，直接拿到的就是v自己的入边列表，根本不会碰其他顶点的边。
哪怕代码没有在找到满足d[v] == d[u] + wgt的父边后立刻跳出循环，继续遍历完v的剩余入边，总遍历的边数依然是m，仅增加了常数次判断，不会改变复杂度的线性量级。

书中给出的解释逻辑完全成立：整个过程每个顶点仅被访问1次，每条边仅被遍历1次，没有额外的重复遍历开销。

对应实现代码的复杂度标注：

def shortest_path_tree(g, s, d):
    """Reconstruct shortest-path tree rooted at vertex s, given distance map d.
    
    Return tree as a map from each reachable vertex v (other than s) 
    to the edge e=(u,v) that is used to reach v from its parent u in the tree.
    """
    tree = {}
    for v in d:  # 外层遍历所有顶点，合计O(n)开销
        if v is not s:
            # 每个v的入边遍历次数累加等于总边数m，内层合计O(m)开销
            for e in g.incident_edges(v, False):
                u = e.opposite(v)
                wgt = e.element()
                if d[v] == d[u] + wgt:
                    tree[v] = e
    return tree

举个最直观的例子：一个有1000个顶点、2000条边的稀疏图，平均每个顶点的入边只有2条，整个代码的内层循环总执行次数就是2000次，加上外层1000次循环，总操作数才3000次，远达不到n*m=200万次的量级。

内容的提问来源于stack exchange，提问作者KamuiYato