Floyd-Warshall algorithm utilizes _____ to solve the all-pairs shortest paths…
2015
Floyd-Warshall algorithm utilizes _____ to solve the all-pairs shortest paths problem on a directed graph in ____ time.
- A.
Greedy algorithm, 𝜃(𝑉3)
- B.
Greedy algorithm, 𝜃(𝑉2 𝑙𝑔𝑛)
- C.
Dynamic programming, 𝜃(𝑉3)
- D.
Dynamic programming, 𝜃(𝑉2 𝑙𝑔𝑛)
Attempted by 230 students.
Show answer & explanation
Correct answer: C
Answer: Floyd–Warshall uses dynamic programming and runs in Θ(V^3) time.
Why: The algorithm maintains a V×V distance matrix and, for each vertex considered as an intermediate node, it updates distances for every ordered pair of vertices. This results in three nested loops over the vertex set, giving time complexity Θ(V^3).
Initialize the distance matrix dist where dist[i][j] = weight(i,j) if the edge exists, dist[i][i] = 0, and dist[i][j] = ∞ otherwise.
For each vertex k from 1 to V, for each i from 1 to V, for each j from 1 to V, set dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). This is the core dynamic programming update.
After the loops complete, dist[i][j] holds the length of a shortest path from i to j using intermediate vertices in {1..V}.
Time complexity: Θ(V^3) due to three nested loops over vertices.
Space complexity: Θ(V^2) to store the distance matrix.
Handles negative edge weights but not negative cycles. A negative cycle is detected if any dist[i][i] < 0 after the algorithm finishes.