Bellmann Ford Algorithm closed

Question

Consider following with respect to directed graph where there can be positive,negative edge weights but no negative edge cycle.

S1 : The Bellmann Ford algorithm will compute correctly the shortest path from source vertex S to every other Vertex.

S2 : The Floyd Warshall algorithm will compute correctly the shortest path between every pair of Verices.

Which of Following statements are Correct ?

A. Only S1

B. Only S2

C. Both

D. None

Comments

there is no negative cycle ===> Bell-man ford and Floyd-warshall give the correct results but dijkstra may not give correct results sometimes

---

C) both

Shaik Masthan

as per my knowledge dijkstra always gives correct result but if in a graph there's is negative edge cycle then it's not detect the negative edge cycle.. ..otherwise it's always gives correct result

---

@Magma

if there are negative edges, You can't guarentee that Dijksta works correctly....

negative weight cycle means, the sum of weight of edges in the cycle leads to negative... if there is a negative cycle then by looping in the cycle infinite times your cost will decrease to -Infinity.

∴ Negative weight cycle present, we can't find the shortest path with any algorithm even by manually also..

---

Thats the trick here according to me the answer should be both but they also considered that the graph can be disconnected so Bellmann ford can fail. But they say that floyd warshall works.

My doubt is if graph can be disconneceted then how can floyd warshall give correct result ?

---

Dijkstrash wont work thats absolutely correct both in case of presence of negative cycle and in presence of negative weight edge also

---

Bellman ford fails to work only if the graph contain negative weight cycles that are not reachable from the source which happens when the graph is disconnected. But here it is already mentioned in the question that there are no negative edge cycles in the graph. So answer should be both of them are correct.

---

duplicate of https://gateoverflow.in/179546/shortest-path-bellman-ford-and-floyd-warshall

Answer 1

https://gateoverflow.in/179546/shortest-path-bellman-ford-and-floyd-warshall