Dijkstra's Algorithm and Cycles

Question

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.

Pincer

If you are referring to the "shortest path algorithm", of course it works for cyclic graphs... Your quoting is false. – Duodenitis

Which book, if I may ask? It would be great if you could provide more details where to find such a quote. – Vilipend

Answer 1

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:

Listless

I'm reading your book too. But I found that if I keep a processed array for tracing the node that had been calculated, it also works for cycle with negative weight. If it will not go back to a node which has been marked as processed, it would not get stuck in a cycle. I am confused. I had some experiments [here](s3-ap-southeast-1.amazonaws.com/image-for-articles/… ) – Synchromesh

As @Henry mentioned in another comment, Dijkstra's won't work on any graph with negative weight edges, even if graph is acyclic: https://mcmap.net/q/452634/-dijkstra-39-s-algorithm-on-directed-acyclic-graph-with-negative-edges – Maroon

Answer 2

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.

Dna

Answer 3

In case someone is looking for an example DAG with negative weights where Dijkstra does not give the correct shortest path: https://mcmap.net/q/129685/-negative-weights-using-dijkstra-39-s-algorithm

Qualitative