CODEWITHSUNDEEP
algorithmgraph-algorithmdijkstra
sam
sam

Reputation: 787

Dijkstra's Algorithm and Cycles

It's stated in a book that "Dijkstra's algorithm only works with Directed Acyclic Graphs".

It appears the algorithm works for graphs with cycles too as long as there are no negative cycles. Is that correct?

Edit 1: The book "Grokking Algorithms" -Aditya Bhargava. Chapter 7. Page 122.

Upvotes: 34

Views: 24875

Answers (3)

Nikhil
Nikhil

Reputation: 123

In case someone is looking for an example DAG with negative weights where Dijkstra does not give the correct shortest path: http://stackoverflow.com/a/6799344/3924118

Upvotes: 2

Aditya Bhargava
Aditya Bhargava

Reputation: 659

I'm the author of Grokking Algorithms. Sorry for this error—Dijkstra's algorithm does work on graphs with cycles, as long as it is a positive weight cycle. I have updated the errata page to reflect this error. Dijkstra's doesn't work on negative weight cycles, and here's an image that explains why:

dijkstra's algorithm with a negative weight cycle

Upvotes: 65

Henry
Henry

Reputation: 43728

Actually, it works as long as all edge weights are non-negative. This is a stronger condition as "no negative cycles". On the other hand it would not work on a DAG with negative weights. So, provided you cited correctly, the statement from the book is wrong for two reasons.

Btw. if you have negative cycles, there may no longer be a shortest path since you may cycle an infinite number of times and go down with your cost as much as you like.

Upvotes: 11

Related Questions