Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

confusion about dijkstra algorithm?

According to the Algorithms book Corman, Dijkstra is applicable for only those graphs whose all edges have non negative weights. Does that mean, if there is any edge with negative weight it will not work for whole of the graph? or Will it not count that negative weight edge? Please indicate which one is right?

like image 915
Shubhanshu Avatar asked Mar 22 '23 20:03

Shubhanshu


1 Answers

Dijkstra algorithm can work on a graph of some negative edges sometimes,like:

A-->B-->C

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

But when there is at least one negative edge, it can't prove to be always right. like:

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 sourcepoint, you will get the length of shortest path from A to D is 2 by Dijkstra algorithm, not -1 in fact.

It is because that Dijkstra algorithm is a greedy algorithm, and its proof procedure of correctness uses that all its edges is non-negative to obtain a contradiction. About its proof procedure, you can look it up at Theorem 24.6 (Correctness of Dijkstra’s algorithm) ,Introduction to Algorithm.

like image 51
vvy Avatar answered Apr 06 '23 00:04

vvy