Questions: Floyd-Warshall Algorithm for All-Pairs Shortest Paths

Question 1

In Floyd-Warshall's triple-nested loop, why must k (the intermediate vertex index) be the outermost loop?

• A. Because the algorithm processes vertices in decreasing order of their weights, which requires k to be fixed first
• B. Because updating dist[i][j] via intermediate vertex k requires that dist[i][k] and dist[k][j] already reflect the best paths using intermediates 1 through k-1 — the k dimension must be fully processed first
• C. Because j must complete all updates before k can be incremented, and k controls the j-loop range
• D. To avoid overwriting distance values needed for other pairs in the same pass of the i and j loops

Answer: (B)

This is the most important implementation detail. The recurrence is dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j]). When computing whether vertex k improves the path from i to j, the algorithm needs the best distances from i to k and from k to j using only intermediates 1..k-1 — values from the previous iteration of k. If k were an inner loop, it would be updating dist[i][k] and dist[k][j] while still using those values for other pairs in the same k-pass, violating the DP dependency structure. Making k outermost ensures each layer is fully computed before the next.

Question 2

After running Floyd-Warshall, you check the result matrix and find that dist[5][5] = -8. What does this indicate?

• A. Vertex 5 has a self-loop with weight -8 that was part of the input graph
• B. The matrix was initialized incorrectly — dist[i][i] should always remain 0
• C. Vertex 5 lies on a negative-weight cycle; the path from 5 back to itself can be made arbitrarily short
• D. Floyd-Warshall detected that 5 is unreachable from itself and assigned a sentinel value

Answer: (C)

Initially, dist[i][i] = 0 for all i. During the algorithm, if a path from vertex i back to i can be improved (i.e., passes through a negative-weight cycle), the diagonal entry becomes negative. A negative value at dist[v][v] signals that v is on a negative-weight cycle. In such graphs, shortest paths are undefined for any pair (i,j) where a path between them passes through this cycle — you can loop it infinitely to reduce the cost without bound. The algorithm detects the cycle but cannot compute valid shortest paths in its presence.

Question 3

Floyd-Warshall correctly computes shortest paths in graphs containing negative-weight edges, as long as no negative-weight cycles exist.

• T. True
• F. False

Answer: True

This is a key advantage over Dijkstra's algorithm, which breaks on negative edges because its greedy strategy assumes that once a vertex is finalized, no shorter path exists — an assumption violated by negative edges. Floyd-Warshall uses exhaustive dynamic programming: it tries all combinations of intermediate vertices for every pair (i,j), so it correctly finds paths that become shorter by taking a detour through a negative-weight edge. Negative cycles are a different problem — they make shortest paths undefined (unbounded), and Floyd-Warshall detects them via the diagonal check but cannot produce valid distances.

Question 4

For sparse graphs (few edges), Floyd-Warshall is generally faster than running Dijkstra's algorithm once from nearly every vertex.

• T. True
• F. False

Answer: False

Floyd-Warshall always runs in O(V³) time regardless of the number of edges. Dijkstra with a binary heap runs in O((V + E) log V) per source, so running it from all V sources costs O(V(V + E) log V). For sparse graphs where E ≪ V², this is much less than O(V³). For example, on a sparse graph with E = O(V), repeated Dijkstra costs O(V² log V) versus Floyd-Warshall's O(V³). Floyd-Warshall becomes competitive only for dense graphs (E ≈ V²), where its simplicity and constant factors make it practical, or when negative edges prevent Dijkstra from being used.

Question 5

Explain the dynamic programming recurrence in Floyd-Warshall: what is dist_k[i][j], and why does progressively expanding the set of allowed intermediate vertices correctly compute all-pairs shortest paths?

Model answer: dist_k[i][j] is the length of the shortest path from vertex i to vertex j using only vertices 1 through k as intermediate vertices. The recurrence is: dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j]). By starting with k=0 (direct edges only) and expanding to k=V, the algorithm considers every possible intermediate vertex exactly once, building optimal sub-paths into optimal full paths.

The DP insight is that any shortest path either does not pass through vertex k (so dist_{k-1}[i][j] is already optimal) or does pass through k (so it splits into two sub-paths, each using only intermediates 1..k-1, which have already been optimized). This exhaustive enumeration over intermediate vertex sets is what allows negative edges: unlike Dijkstra's greedy approach, there is no assumption that the nearest vertex is settled. Every pair is reconsidered at each expansion of k.