0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What is the worst-case running time of your algorithm? Can you prove it? $\endgroup$ – D.W. Mar 26 '20 at 8:04
  • $\begingroup$ I guess it's more than O(V+E), but what problem topological sort solves? $\endgroup$ – vivek gupta Mar 26 '20 at 8:37
  • 1
    $\begingroup$ Don't guess -- prove it. If it turns out to be more than O(V+E), you have your answer, don't you? What's the running time if you do use a topological sort? $\endgroup$ – D.W. Mar 26 '20 at 19:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.