CODEWITHSUNDEEP
algorithmshortest-pathdijkstra
Y.T.
Y.T.

Reputation: 2768

Find shortest path in graph algorithm

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?

Upvotes: 3

Views: 272

Answers (2)

Y.T.
Y.T.

Reputation: 2768

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

Upvotes: 0

Tobias
Tobias

Reputation: 2575

..., 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)

Upvotes: 1

Related Questions