edited by
3,084 views
5 votes
5 votes

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?

edited by

3 Answers

3 votes
3 votes
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.
0 votes
0 votes
Both true
0 votes
0 votes

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

Related questions

2 votes
2 votes
4 answers
1
Bongbirdie asked Apr 6, 2017
1,810 views
Is the below statement correct:Bellman Ford finds all negative weight cycles in the graph.This is true or false?
0 votes
0 votes
0 answers
2
srestha asked Aug 26, 2018
665 views
What are the asymptotic running times for INSERT, EXTRACT-MIN, and DECREASE-KEY of Floyd Warshall and Bellman Ford Algorithm?
0 votes
0 votes
2 answers
4