Self doubt

Question

What is the difference between Dijkstra and Bellman Ford algorithm?

Will the shortest path given by both be same in following conditions :

a) All positive edge weights

b) Some negative edge weights without negative edge cycle

c) With negative edge cycles

Comments

For options a and b it will be same

It will different for option c

---

Give explanation also.

---

Will both algorithms give optimised shortest path if all weights are positive?

Since Bellman Ford uses dynamic programing it will give  is optimal path isn't it ?

---

Yes the paths will be same if we have +ve weights and -ve weights except for negative weight cycles.
Bellman Ford has the capability to find the -ve weight cycles by performing the shortes path method n th time and comparing with n-1th and see if any changes to last state values.
Time complexity :
Dijkstra O(ElogV)--> Uses Gready Strategy
Bellman fordO(VE)-->Uses Dynamic Programming

---

@Hemanth_13

Bellman Ford has the capability to find the -ve weight cycles by performing the shortest path method n th time and comparing with n-1th and see if any changes to last state values.

where you read this statement ?

 

let there are two vertices, A nd B, A to B is 5 and B to A is -10,

then what is the shortest path between A and B?

---

How does this work? Like other Dynamic Programming Problems, the algorithm calculate shortest paths in bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-most 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edges 

---

@Shaik Masthan

He is trying to say that if n is the number of vertices If we run Bellmen ford Algo n-1 times Then we can find the shortest path. If we run one more times ( n-1 +1 ) times, If weight is changing then there is a cycle in the graph.

---

provide shortest path between A and B for that example ?

---

@Hemanth_13 @kumar.dilip

what i want to convey is " if there is  a negative cycle, then even Bellmon-Ford can't help. "

 

and moreover 

 Some negative edge weights without negative edge cycle

then in some graphs dijkstra's fails 

---

Yes, I know.

---

If there is only positive edge weights then we can use either dijkstra or bellman Ford is that so?

---

yes...@vipin

Answer 1

If only (+)ve edge weight then both will give correct answer.

If there is (-)ve edge weight only then Dikstra's may or may not give correct answer but bellman ford will give correct answer.

If (-) ve edge weight cycle then bellman ford will report it if it is reachable from source and return answer as undefined.