CODEWITHSUNDEEP
algorithmshortest-pathtopological-sort
WABBIT0111
WABBIT0111

Reputation: 2313

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

I am confused to why topological sorting for shortest path is Big-O of O(V+E). Here is the algorithm: 

1. Topologically sort G into L;
2. Set the distance to the source to 0;
3. Set the distances to all other vertices to infinity;
4. For each vertex u in L
5.    - Walk through all neighbors v of u;
6.    - If dist(v) > dist(u) + w(u, v) 
7.       - Set dist(v) <- dist(u) + w(u, v);

Seem to me it's O(V*E) rather than O(V+E) because it has 2 nested for loops. but according to Wikipedia it's O(V+E), Am I missing something here ? https://en.wikipedia.org/wiki/Topological_sorting#Application_to_shortest_path_finding

Upvotes: 0

Views: 1484

Answers (1)

ahmacleod
ahmacleod

Reputation: 4310

Remember that the edges are directed, so the same edge is never considered for more than one vertex. Despite the nested loop, you end up looking at each vertex and each edge exactly once.

Upvotes: 3

Related Questions