The diykstra confusion?

Question

According to the book of Corman Algorithms, Dijkstra is applicable only to those graphs for which all edges have no negative weights. Does this mean if there is any edge with a negative weight, it will not work for the entire schedule? or Would it count negative weight? Indicate which one is right?

Answer 1

Dijkstra's algorithm can sometimes work on the graph of some negative edges, for example:

A-->B-->C 

while w(A, B) = -1 and w(B, C) = -2 .

But when there is at least one negative edge, it cannot always be correct. as:

 A-->B-->C-->D \ / \ _____ / 

where w(A, B) = 1 , w(B, C) = 3 , w(C, D) = -5 , w(A, D) = 2 .

If you choose A as the starting point, you will get the shortest path length from A to D, will be 2 Dijkstra's algorithms, not -1 .

This is because Dijkstra's algorithm is a greedy algorithm, and its validation routine uses that all its edges are non-negative to get a contradiction. You can find the proof procedure in Theorem 24.6 (The correctness of Dijkstra's algorithm), Introduction to the algorithm.

Answer 2

The main problem with negative edges is negative loops . If the graph contains a negative cycle between the vertex S and the vertex T, then there is no shortest path between S and T. Dijkstra finds the shortest path that is incorrect.

Thus, negative edges are not only ignored, but also contribute to completely false decisions.

An alternative is the Bellman-Ford algorithm, which finds negative cycles in it | V | th iteration.