A strong answer
Floyd-Warshall is a dynamic program over allowed intermediate vertices. The state after round k is: d[i][j] is the shortest path from i to j whose intermediate vertices are all among vertices 0 to k. The recurrence for adding vertex k: the best path either avoids k, keeping the old d[i][j], or passes through it once, giving d[i][k] + d[k][j], where both parts use only intermediates below k.
That recurrence requires every pair's answer for intermediates up to k − 1 to be complete before any pair considers k. With k as the outer loop, that holds: round k reads the matrix as left by round k − 1. With k as the inner loop, each d[i][j] is finalized after checking each k once, but d[i][k] and d[k][j] may not yet include paths through vertices handled later, so multi-hop improvements are missed and some distances come out too large.
The in-place update is safe because during round k, row k and column k don't change: d[k][j] can't improve by passing through k itself, as d[k][k] is 0 (absent negative cycles). Paths come from a next-hop matrix updated whenever a relaxation succeeds. A negative diagonal entry after the loops indicates a negative cycle. The cost is O(n³) time and O(n²) memory, good for dense graphs of a few hundred vertices; for large sparse graphs, Dijkstra from every vertex, or Johnson's algorithm when some weights are negative, is much faster.
What the interviewer is listening for
- The DP state in terms of allowed intermediates.
- Why the recurrence needs k outermost.
- Practical details: in-place updates, path recovery, negative cycles and complexity.
Common mistakes
- Treating the loop order as arbitrary.
- Describing the algorithm as "trying all paths".
- Using it on graphs too large for n³.