0

I am trying to learn Graphs in which i found that to find shortest path from one node to other node we can use Dijkstra and Bellman-ford algorithm.

In which Dijkstra will not work for the Graph which contains negative weight edges. While Brllman-ford can handle such Graph which contains negative weight edges.

My doubt is i tried many kind of Graphs which contains negative weight edge and applied Dijkstra and Bellman-ford both but in all the cases i found the same result i mean no difference, for negative weight edge also dijkstra is working fine. May be my thought process or the way how i am solving is wrong so only i am getting correct answer for dikstra.

My question is can any one explain me a Graph which have negative edge and explain the different result for dijkstra and bellman-ford.

Amit Kumar
  • 93
  • 2
  • 8
  • If source vertex is u then take u to v as cost 5, u to w as cost 6, and w to v as cost -2. – Abhishek Bansal Sep 25 '14 at 16:58
  • Yes, dijkstra as it stands, can give wrong ans. see http://stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm for a beautiful example. – axiom Sep 25 '14 at 16:58

1 Answers1

2

Djikstra algorithm to find the shortest path between two edges can be used only for graphs that have positive weights. To see the difference of answers that bellman-ford and djikstra gives when there is a negative edge weight, lets take a simple example

we have 3 nodes in the graph, A B C
A is connected to B edge weight 4
A is connected to C edge weight 2
B is connected to C edge weight -3

when djikstra is used to calculate shortest path between A and C, we get weight 2

but when bellman-ford is used to calculate the shortest path between A and C, the weight is 1

This is happening because of the fact that djikstra finalises the node which has the minimum edge weight, ignoring the fact that there could be path with less weight to that node (note that this could happen only when negative weights are present. with only positive weights this is not possible).

hope you understood the difference

Haris
  • 12,120
  • 6
  • 43
  • 70
  • Do we keeping the visited node information some where.As in my case i am doing like for the graph you told: A-->B and A --> c weight is 2 and 4.so my priority queue is "CB" then i will delete C.but when i will process B i will get to know that i can reach to C with -1 cost so update the distance an my queue – Amit Kumar Sep 25 '14 at 17:01
  • @AmitKumar: not exactly sure what you asking. the bellman-ford algorithm never removes any vertex during the process, while in djikstra at every iteration the vertex to which the weight is minimum is finalized and added to the shortest path. – Haris Sep 25 '14 at 17:06
  • @AmitKumar: you dont do that in djikstra. once the path that is selected (A-->C) is not changed. – Haris Sep 25 '14 at 17:08
  • I mean to say for Dijkstra initially i have a preority queue filled with A as source.Next adjacent vertex will be "CB".Then i will delete min as C.And now only B is present in the priority queue and my distance table is A->B 4,A -> C 2. Now if i will delete B from my queue and takr tge adjacent vertex i.e. C now so i will check that reaching from B-> C costs me 1 which is minimum from current value od c's disatnce i.e 2.so what i am doing i am updating disatnce of C as 1 and pushing C again to preority queue. – Amit Kumar Sep 25 '14 at 17:17
  • @AmitKumar: That is something djikstra does not do. once the path to something has been decided, it cannot be changed if a less weighted path is found later. its like making a decision at every iteration, and that decision is final. now if you think then, wont it be better if we can change that decision if a less weighted path is found, it is better and thats exactly what bellman-ford is doing. – Haris Sep 25 '14 at 17:24
  • I mean to say for Dijkstra initially i have a preority queue filled with A as source.Next adjacent vertex will be "BC".Then i will delete min as C.And now only B is present in the priority queue and my distance table is A->B 4,A -> C 2. Now if i will delete B from my queue and take the adjacent vertex i.e. C now so i will check that reaching from B-> C costs me 1 which is minimum from current value of c's disatnce i.e 2.so what i am doing i am updating disatnce of C as 1 and pushing C again to preority queue. – Amit Kumar Sep 25 '14 at 17:24
  • Ok so you mean to say that later at any stage we can not modify the path which we have already gave some distance but how do we check tht we have processed that node and the value is final one – Amit Kumar Sep 25 '14 at 17:27
  • @AmitKumar: the nodes remaining in the queue are left to be processed. ones deleted are already processed. – Haris Sep 25 '14 at 17:29
  • @AmitKumar there is a "visited" flag in Dijkstra's algorithm that marks whether a vertex has been visited. distance update only checks those vertices in the adjacency list that are not "visited". By the time the algorithm executes to the point of taking B out of the priority queue, all of B's neighbors have been visited so there is nothing left to do and algorithm will terminate. At this point, C=2 and B=4, the negative edge never gets considered. – NSCoder Jun 14 '16 at 17:49