I know Bellman Ford algorithm works well with negative weighted Graph, But I've developed a code of Dijkstra Algorithm that works very well. But it fails when I insert negative weighted edges. Any Solution?
Asked
Active
Viewed 926 times
1
-
I think it is not possible . you can take a look this queston http://stackoverflow.com/questions/5956534/dijkstras-algorithm-with-negative-weights – htkaya May 12 '13 at 12:21
-
you can use it if your graph is a DAG (directed acyclic graph). – Matthias Kricke May 13 '13 at 12:59
4 Answers
2
I think we can't do that, as Dijkstra algorithm will not find a final way to reach at destination vertex because it may get stuck in loops, it is not made for negative weighted graphs, you should go for bellman ford algorithm
2
Actually, it is possible in a special case. Dijkstra algorithm will fail, if there is an edge of a negative length. However, if all edges are of negative length, then you may inverse the lengths of all edges and use the algorithm to find the longest path between two vertices of the graph (the path will represent the shortest path in the original graph).
But in a general case, as you have stated, it is not possible to use Dijkstra. If there is no cycle of negative length, than you shall use Bellman-Ford algorithm. If you cannot guarantee that there no cycle of negative length, than the problem is NP-complete and there is no known polynomial algorithm.
malejpavouk
- 4,297
- 6
- 41
- 67
-
Good work, Thanks for the link..... I never knew it, Thanx for the exceptional case – Sep 13 '13 at 17:30
1
As you stated, Bellman Ford is the algorithm of choice for finding the shortest path in a graph with negative weights. The issue with using Dijkstra's Algorithm in this scenario is that Dijkstra's assumes that all possible subpaths from s to t in a graph must be smaller than the goal subpath, which is not necessarily true when negative edge weights are added.
yiati
- 995
- 1
- 12
- 27
1
If all edge weights are positive, this guarantees that adding more edges to a path makes it longer. Knowing this, Dijkstra's algorithm will discard any paths that are longer than the shortest one it has found to some vertex since there is no chance of the long path becoming shorter than the short path.
However, this assumption is not true if there are negative edge weights since we could have an extremely long path P that we discarded, but somewhere down the road, P can pass through a very negative edge and become shorter than the shortest path you currently have. Therefore, we can't guarantee that a path we've found is the shortest at any stage in Dijkstra's algorithm, which the algorithm relies on.
Duncan
- 984
- 10
- 20