Find shortest path in graph algorithm

Question

I have just seen this video: https://youtu.be/2E7MmKv0Y24?t=1335
It talks about an algorithm that finds the shortest distance between a source and a given vertex in a DAG:

1.Sort the graph in topological order and express the graph in its linear form
2.Initialize all of the vertex to infinity except the source, which is initialized to 0
3.Iterate from the source to the rightmost vertex. For every vertex u, update the distance of all of its neighbor v to min((distance between source and v), (distance between source and u) + (distance between u and v))

At about 22:00, the professor said that this algorithm works for negative edges but the graph cannot contain cycle, but i think the algorithm works for graphs that contain non-negative cycle. Am I right?

Instead of posting the video, could you put its content here in text-form? What algorithm is he talking about? — Zabuzard
– Zabuzard, Commented Nov 19, 2019 at 8:36

Tobias · Accepted Answer · 2019-11-19 08:47:24Z

1

..., but i think the algorithm works for graphs that contain non-negative cycle. Am I right?

Yes, you're right. See this post for more information.

Another question is why do I need to topologically sort the array first? Why can't I just loop through every neighbour and calculate the distance to them?

If I understood the question correctly you can't go to just any next node because there could be a shorter way to this node using another node first (e.g. the cost to reach a node is 5 and there is another way to the node using two nodes that uses a cost of 1 + 1 = 2; If you don't sort first in this case you would use the wrong path)

answered Nov 19, 2019 at 8:47

Tobias

2,5753 gold badges17 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Y.T. · Accepted Answer · 2020-07-28 17:25:03Z

0

I realised that I was not correct apparently. If the graph has cycles then topological sort isn't possible.

answered Jul 28, 2020 at 17:25

Y.T.

2,8162 gold badges17 silver badges34 bronze badges

Collectives™ on Stack Overflow

Find shortest path in graph algorithm

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related