Clever Geek Handbook

Dijkstra's algorithm and cycles

The book said that "Dijkstra's algorithm only works with Directed Acyclic Graphs."

The algorithm seems to work for plots with cycles as well if there are no negative cycles. It is right?

Edit 1: Book "Grokking's Algorithms" by Aditya Bhargava. Chapter 7. Page 122.

+3


source to share


2 answers


I am the author of Grokking algorithms. Sorry for this error. Dijkstra's algorithm works on charts with cycles if it is a positive weight cycle. I have updated the error page to reflect this error. Dijkstra does not work on negative weights, but here is an image that explains why:



dijkstra's algorithm with a negative weight cycle

+7


source


In fact, it works as long as all edge weights are non-negative. This is a stronger condition known as "negative cycles". On the other hand, it will not work on DAGs with negative weights. So, if you put it right, the expression in the book is wrong for two reasons.



Btw. if you have negative cycles it may not be the shortest path anymore, as you can do an infinite number of times and go with your cost as much as you want.

+4


source






More articles:


All Articles