Complexity of reconstructing shortest path tree of Djikstra Algorithm

Question

I am currently reading Data Structures and Algorithms in Python and I am in Chapter 14 page 669. The book says that reconstructing a shortest path tree takes O(n+m) time. but given the code I couldn't understand why it's O(n+m) and not O(n*m) (because we have two nested for loops one over the vertices and the other over the incoming edges.)

The book says:

In this section, we demonstrate that the shortest-path tree rooted at source s can be reconstructed in O(n + m) time, given the set of d[v] values produced by Dijkstra’s algorithm using s as the source. As we did when representing the DFS and BFS trees, we will map each vertex v =/= s to a parent u (possibly, u = s), such that u is the vertex immediately before v on a shortest path from s to v. If u is the vertex just before v on the shortest path from s to v, it must be that d[u] + w(u, v) = d[v]. Conversely, if the above equation is satisfied, then the shortest path from s to u, followed by the edge (u, v) is a shortest path to v. Our implementation reconstructs the tree based on this logic, testing all incoming edges to each vertex v, looking for a (u, v) that satisfies the key equation. The running time is O(n + m), as we consider each vertex and all incoming edges to those vertices.

and here is the code of the implementation:

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

Thank you!

Answer 1

Lets consider pseudocode for the code you showed:

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

You can see that each edge adds one more visit to a node.

imagine m = 0, the exact number of visits is number of nodes

imagine m = 1, the exact number of visits is number of nodes + (1 more time each for the two nodes connected by the edge)

therefore number of visits = number of nodes + number of edges and hence the complexity of O(n + m)