Let's say Dijkstra is run from a random vertex and it meets a negative-weight cycle on the path. We can loop around the cycle to make the cost as small as possible, but Dijkstra's invariant is not to "re-visit" the visited nodes, so I suppose there won't be an infinite loop and Dijkstra would terminate?
Asked
Active
Viewed 847 times
1 Answers
0
The problem isn't that Dijkstra's algorithm wouldn't terminate, it's that Dijkstra's algorithm doesn't work on graphs with negative weights at all. See this answer for an explanation of why.
-
but is there a way to detect a negative cycle in a graph using Dijkstra then? – Mariska Mar 24 '13 at 05:50
-
@Mariska You shouldn't be running Dijkstra's on graphs that might have negative weights. So, no, there is not. – Xymostech Mar 24 '13 at 05:55