CODEWITHSUNDEEP
algorithmgraph
Amit Kumar
Amit Kumar

Reputation: 93

Dijkstra vs Bellman- ford A Directed Graph which will give different result

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.

Upvotes: 0

Views: 3185

Answers (1)

Haris
Haris

Reputation: 12272

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

Upvotes: 2

Related Questions