Dijkstra's Algorithms and Negative Weights and Cycle
I study on Greedy Algorithm. summarize some important aspects about Dijkstra's Algorithms, that will be TRUE. i suspect about (4) and (1), anyone could help me?
I) if all edges weight be negative, the Dijkstra's algorithm, works well.
II) if in graph we have a negative cycle, Dijkstra's get into a infinite loop and never end.
III) if a graph has a one edge with negative weight, but hasn't a negative cycle, the algorithm doesn't works well.
IV) if graph hasn't a negative cycle, the algorithms work well.
Dijkstra's algorithm only works on graphs with non-negative edges. This is because it assumes that the first time a node is popped off the queue we have found the shortest path to that node and this is not necessarily true as soon as you have even one negative weight.
Therefore I is false, II is false (because the negative cycle may not necessarily be reachable), III is true, IV is false (it may still have a negative edge even without a negative cycle).
If I remember it correctly Dijkstra's algorithm (at least the classic version of it) has a built in assumption that all weights in a graph are non-negative. So we have no guarantee that it will work correctly if we have negative edges in our graph.
I) In the first case we will most likely get a longest possible chain of edges with highest absolute values of weights as the shortest path, technically this will be the correct shortest path. (I assume the graph has no negative cycles)
II) False as negative cycle may be unreachable (as Peter de Rivaz correctly said)
III-IV) I assume that the 3rd paragraph is about graph having one edge with negative weight, but hasn't a negative cycle. In this case there is a possibility of algorithm stucking in a loop, because it can find a cycle with a negative-weight edge that will seem to an algorithm as a good path prolongation beacuse at some point in algorithm we decide on the next step on the weight of one edge. The negative one will always be the first choice no doubt, so even with a non-negative cycle we getting a possibility of infinite looping.
链接地址: http://www.djcxy.com/p/35246.html上一篇: Dijkstra的负权重算法
下一篇: Dijkstra的算法和负权重和周期