algorithm - Why is Topological Sorting to find the shortest path O(V+E) -


i confused why topological sorting shortest path big-o of o(v+e). here algorithm:

1. topologically sort g l; 2. set distance source 0; 3. set distances other vertices infinity; 4. each vertex u in l 5.    - walk through neighbors v of u; 6.    - if dist(v) > dist(u) + w(u, v)  7.       - set dist(v) <- dist(u) + w(u, v); 

seem me it's o(v*e) rather o(v+e) because has 2 nested loops. according wikipedia it's o(v+e), missing here ? https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding

remember edges directed, same edge never considered more 1 vertex. despite nested loop, end looking @ each vertex , each edge once.


Comments