I was wondering why do we need to do the topological sort before performing relaxing of edges.
Wouldn't it'd be better if we do : if starting vertex is "s"
queue.add(s)
while(the queue is not empty)
for every adjacent vertex v of u
if( dist[v] > dist[u] + weight(u,v) )
dist[v] = dist[u] + weight(u,v)
add v to the queue
I had intentionally left out visited[] array
By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times.
queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue
But by using the topological sorting, we get the order in which the vertices should be traversed so that an edge is visited exactly once. So we could have guaranteed T.C. of O(V+E).
###So to solve this problem to work in O(V+E) we use topological sort.###
But I think this is not enough, we should also know why to use Topological ordering here and so that it helps in other problems.
##Why Topological ordering ?##
Topological ordering gives us the order like 0 1 2 3 4 5 then, once we reach a node in this ordering (let's say 4) then we've already computed the shortest path to it (4) as all the edges(as well as paths) of type u -> v (v = 4) and have already been visited.
Toposort also work as a visited array and prevent from getting into a cycle where every time your distance increases.
0 ---> 2 ---> 0
Now, you are thinking: why don't we use a visited array instead of toposort? You can't use a visited array because you don't know when your distance will increase, but using toposort you get to know which vertices will be filled first and then later on.
