Menu
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.
563
Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph. It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph.
Dijkstra Algorithm is a graph algorithm for finding the shortest path from a source node to all other nodes in a graph(single-source shortest path). It is a type of greedy algorithm. It only works on weighted graphs with positive weights.
Since Dijkstra's goal is to find the optimal path (not just any path), it, by definition, cannot work with negative weights, since it cannot find the optimal path.
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:
84
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.
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
