算法最短路径树重构的复杂性

Question

我目前正在阅读Python中的数据结构和算法，我在第14章第669页。书中说，重建最短路径树需要O(n+m)时间。但是，考虑到这些代码，我无法理解为什么它是O(n+m)而不是O(n*m) (因为我们有两个嵌套的for循环，一个嵌套在顶点上，另一个嵌套在传入边上)。

书上说：

在这一部分中，我们证明了基于源s的最短路径树可以在O(n + m)时间内重建，给出了Dijkstra算法以s为源产生的dv值集。正如我们在表示DFS和BFS树时所做的那样，我们将每个顶点v =/= s映射到父u(可能的话，u= s)，这样u就是从s到v最短路径上v之前的顶点，如果u是从s到v最短路径上的顶点，则必须是du + w(u，v) = dv。相反，如果满足上述方程，则从s到u的最短路径，然后是边(u，v)是v的最短路径。我们的实现基于这个逻辑重新构造树，测试每个顶点v的所有传入边，寻找满足关键方程的(u，v)。运行时间为O(n + m)，因为我们考虑到这些顶点的每个顶点和所有传入的边。

下面是实现的代码：

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:
        if v is not s:
            for e in g.incident_edges(v, False):      # consider INCOMING edges
                u = e.opposite(v)
                wgt = e.element()
                if d[v] == d[u] + wgt:
                    tree[v] = e                       # edge e is used to reach v
    return tree

谢谢!

Answer 1

让我们考虑一下您展示的代码的伪代码：

for each node 
      visit node
      get its edges
        visit the node connected

您可以看到，每个边都会对节点再添加一次访问。

假设m= 0，访问的确切次数是节点数。

假设m= 1，访问的确切次数是节点数+(由边连接的两个节点各多1次)

因此访问次数=节点数+边数，从而导致O(n + m)的复杂性。