Shortest path - bellman ford and floyd warshall

Question

Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles:
S1  : The Bellman-Ford algorithm correctly computes shortest path lengths from a given origin ‘s’ to every other vertex ‘v ’.
S2 : The Floyd-Warshall algorithm correctly computes shortest path lengths between every pair of vertices.
Which of them is correct?

Comments

@MIRIYALA Answer given in made easy is wrong. Even when the graph is disconnected, Floyd-Warshal algo will contain an infinity in it final matrix(representing there is no way) if the initial matrix was such that there is infinity in D[u, v] if there is no edge between u and v. 

---

I dont think you take question correctly:

Consider the following statements with respect to a directed graph G in which edges can have positive or negative edge length but that has no negative cycles: 
S₁  : The Bellman-Ford algorithm correctly computes shortest path lengths from a given origin ‘s’ to every other vertex ‘v ’. 

Lets take 1^st one : Yes  :Now if you take disconnected graph then graph has path b/w every vertex? No so graph can give the shortest path only b/w those vertices which have path initially.

So you cannot expect from Bellman ford that he will connect two vertexes, it programmer error that he give wrong input and expect correct output.
 

S₂ : The Floyd-Warshall algorithm correctly computes shortest path lengths between every pair of vertices. 

If bellman ford can do it then why cant Floyd warshal.

Here correctly compute the shortest path means if the original graph has two paths then it give the best path , but if graph itself hasnt the path then the algorithm will show only infinite.

---

@Anu007:

 

Bellman ford algorithm first assume all the distance from source vertex to every other vertex as infinity, then we relax the edges |V-1| times and if there exist no path then the length still remains infinite.

Similarly in Floyd Warshall Also the initial matrix will contain infinity for a node to every other node except itself if there is no edge between them.

both statements are correct

Answer 1

Both will be correct.

S1. Bellman Ford works correctly if there are no negative weight cycles

S2. Floyd Warshall Algorithm uses Dynamic programming , therefore all the possiblities will be considered. So given that if shortest path exist(i.e., no negative weight cycles), then Floyd Warshall will surely find it.

Answer 2

Both true

Comments

@Vikash, when the graph has contained negative cycle at that time belmanford, will not find the minimum.

But both option is true here.

Answer 3

Bellman Ford is compatible even if there are negative edges or negative edge cycles, to find the Single Source Shortest Path.

Time Complexity: O(V^2)

Whereas The Floyd -Warshall Algorithm is Used to find all Pair Shortest Path.

Time Complexity: O(V^3)

BOTH ARE TRUE