my current understanding is that dijkstra's algorithm is more efficient then bellman-ford, only it cannot handle negative edges. However say we have an edge weighted graph where there are negative-weight edges, there are no negative-weight cycles in the graph, can we still use dijkstra's algorithm?
Asked
Active
Viewed 309 times
1
-
1Possible duplicate of [this](https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges) or [this](https://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm/6799344#6799344) question. – Codor Nov 28 '19 at 07:22
-
This looks like a great question for https://cs.stackexchange.com/ – David Buck Nov 28 '19 at 07:30
1 Answers
0
This question has already been answered well here. https://stackoverflow.com/a/13159425/12449779
To summarize, Dijkstra's algorithm in each iteration marks the vertices at minimum distances from "marked" vertices. Initially, the source vertex is the only marked vertex with distance 0. Suppose two marked vertices exists A and B who are at a certain finite distance from source and their paths do not overlap. Currently, the paths to A and B would be considered as the shortest possible paths from A to B. Since the paths do not overlap, any path from Source to A to B would be of length source to A + length of Path from A to B which is greater than path from source to B as paths from source to A and B do not overlap. But if negative weighted edges are allowed, this does NOT hold. As the length of path from A to B may be negative. Thus Dijkstra's Algorithm does not work. There is no simple way to convert a general graph with negative edges to one with non-negative edges either. Bellman Ford works for any graph which does not contain negative weighted cycles.
Ayan
- 36
- 4