Question

Which one of the following statements about Floyd's algorithm running on a graph with V nodes and E edges is correct?

Group of answer choices

The iterative (dynamic programming) version finds the shortest path between all pairs of nodes in time O(V³)

The recursive version finds the transitive closure of a graph in O(3^V) time.

The iterative (dynamic programming) version finds the shortest path between all pairs of nodes in O(3^E) time

The iterative (dynamic programming) version always finds a minimal spanning tree rooted at every node in O(V³) time.

Answer 1

Correct Option: The iterative (dynamic programming) version finds the shortest path between all pairs of nodes in time O(V³).

Explanation:

The Floyd–Warshall algorithm (also known as Floyd's algorithm) is an algorithm for finding all pair shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).

Algorithm:

V = nunber of vertices

A = matrix of dimension V*V

for k = 1 to V

    for i = 1 to V

        for j = 1 to V

            A^k[i, j] = min (A^k-1[i, j], A^k-1[i, k] + A^k-1[k, j])

return A

So here three for loops are running. So, the complexity is O(V³).