Why does Dijkstra's algorithm fail on a negative weighted graphs? Asked 7 years, 10 months ago. Active 3 years, 1 month ago. Viewed 73k times. Improve this question. Look into Johnson's algorithm, that should give you a good idea about this problem.
There are walks from A to B of weight -1, -3, -5, If all weights are positive, then the shortest walk is a path, so we don't have to worry about the difference. If we have negative weights, we have to be very careful about what we want; the Bellman-Ford and Floyd-Warshall algorithms do different things. Add a comment. Active Oldest Votes.
Improve this answer. David Richerby David Richerby It requires 1 that the destination is not reachable from the cycle, and 2 that the destination is reached before any element of the cycle. So if x is a visited neighbour of u , the path is not even considered as a possible shorter way from source to v. In our example above, C was a visited neighbour of B, thus the path was not considered, leaving the current shortest path unchanged. This is actually useful if the edge weights are all positive numbers , because then we wouldn't waste our time considering paths that can't be shorter.
So I say that when running this algorithm if x is extracted from Q before y , then its not possible to find a path - which is shorter. Let me explain this with an example,. And as we already assumed that the edge weights are positive, i.
So the alternative distance alt via y is always sure to be greater, i. So the value of dist[x] would not have been updated even if y was considered as a path to x , thus we conclude that it makes sense to only consider neighbors of y which are still in Q note comment in line So any dist[x] calculation we make will be incorrect if x is removed before all vertices v - such that x is a neighbour of v with negative edge connecting them - is removed.
So in the example I gave above, the mistake was because C was removed before B was removed. While that C was a neighbour of B with a negative edge! Just to clarify, B and C are A's neighbours. B has a single neighbour C and C has no neighbours. Dijkstra's algorithm assumes paths can only become 'heavier', so that if you have a path from A to B with a weight of 3, and a path from A to C with a weight of 3, there's no way you can add an edge and get from A to B through C with a weight of less than 3.
This assumption makes the algorithm faster than algorithms that have to take negative weights into account. We have 2 sets of vertices at any step of the algorithm. Set A consists of the vertices to which we have computed the shortest paths.
Set B consists of the remaining vertices. Inductive Hypothesis : At each step we will assume that all previous iterations are correct. Inductive Step : When we add a vertex V to the set A and set the distance to be dist[V], we must prove that this distance is optimal. If this is not optimal then there must be some other path to the vertex V that is of shorter length. Try Dijkstra's algorithm on the following graph, assuming A is the source node and D is the destination, to see what is happening:.
Note that you have to follow strictly the algorithm definition and you should not follow your intuition which tells you the upper path is shorter.
The main insight here is that the algorithm only looks at all directly connected edges and it takes the smallest of these edge. The algorithm does not look ahead. You can modify this behavior , but then it is not the Dijkstra algorithm anymore.
This algorithm wont give the correct result in the following case with a -ve edge where A is the source vertex:. Here, the shortest distance to vertex D from source A should have been 6.
But according to Dijkstra's method the shortest distance will be 7 which is incorrect. Also, Dijkstra's Algorithm may sometimes give correct solution even if there are negative edges. Following is an example of such a case:. However, It will never detect a negative cycle and always produce a result which will always be incorrect if a negative weight cycle is reachable from the source , as in such a case there exists no shortest path in the graph from the source vertex.
Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" and out of the open set - it assumes that any node originating from it will lead to greater distance so, the algorithm found the shortest path to it, and will never have to develop this node again, but this doesn't hold true in case of negative weights.
You can use dijkstra's algorithm with negative edges not including negative cycle, but you must allow a vertex can be visited multiple times and that version will lose it's fast time complexity. In that case practically I've seen it's better to use SPFA algorithm which have normal queue and can handle negative edges. The other answers so far demonstrate pretty well why Dijkstra's algorithm cannot handle negative weights on paths.
But the question itself is maybe based on a wrong understanding of the weight of paths. If negative weights on paths would be allowed in pathfinding algorithms in general, then you would get permanent loops that would not stop. Any pathfinding algorithm would have to continuously loop between B and C because doing so would reduce the weight of the total path. So allowing negative weights for a connection would render any pathfindig algorithm moot, maybe except if you limit each connection to be used only once.
So, what's the perfect path? Any time the algorithm adds a BC step, it reduces the total weight by 2. 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. Dijkstra will actually not loop, since it keeps a list of nodes that it has visited.
But it will not find a perfect path, but instead just any path. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. And as we already assumed that the edge weights are positive, i. So the alternative distance alt via y is always sure to be greater, i. So the value of dist[x] would not have been updated even if y was considered as a path to x , thus we conclude that it makes sense to only consider neighbors of y which are still in Q note comment in line So any dist[x] calculation we make will be incorrect if x is removed before all vertices v - such that x is a neighbour of v with negative edge connecting them - is removed.
So in the example I gave above, the mistake was because C was removed before B was removed. While that C was a neighbour of B with a negative edge!
Just to clarify, B and C are A's neighbours. B has a single neighbour C and C has no neighbours. Dijkstra's algorithm assumes paths can only become 'heavier', so that if you have a path from A to B with a weight of 3, and a path from A to C with a weight of 3, there's no way you can add an edge and get from A to B through C with a weight of less than 3.
This assumption makes the algorithm faster than algorithms that have to take negative weights into account. Python Javascript Linux Cheat sheet Contact. Why doesn't Dijkstra's algorithm work for negative weight edges?
But with negative weights - it might not be true. Consider the graph shown below with the source as Vertex A.
0コメント