Complexity of reconstructing shortest path tree of Djikstra Algorithm-CodePudding

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!

CodePudding user response：

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)