Shortest Path

Floyd-Warshall

Find shortest paths between ALL pairs of nodes. For each intermediate node K, check if going through K shortens the path from i to j: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]). O(V³). Use for small, dense graphs.

O(V³)

O(V²)

say this out loud

I need every pair, not one source, so Floyd-Warshall: for each intermediate node k, check whether routing through it is shorter. O(V cubed) but trivial to write.

How It Works

Floyd-Warshall solves all-pairs shortest paths with dynamic programming over intermediate vertices. Define dp[i][j] as the shortest distance from i to j using only intermediate nodes drawn from the first k vertices. For each candidate intermediate k, either the best i→j path avoids k, or it splits into i→k plus k→j: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]). Three nested loops (k outermost) fill the table in place.

The runtime is O(V³) with O(V²) space, which beats running Dijkstra from every source only on dense graphs or when V is small (a few hundred nodes). It tolerates negative edges as long as no negative cycle exists, and a negative value on the diagonal dp[i][i] after completion reveals such a cycle. Its simplicity (no heaps, no adjacency lists) makes it easy to code correctly under pressure.

Step-by-Step Visualization

Three nodes, edges 0 to 1 costing 3, 1 to 2 costing 1, and 2 to 0 costing 7. The matrix reads row i to column j

∞

known3 direct edges

1/7

Code

Java

static void floydWarshall(int[][] dist) {
  int n = dist.length;

  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];
}

// Initialize: dist[i][j] = weight or INF, dist[i][i] = 0

Tips & Gotchas

1Triple nested loop: for each intermediate node k

2dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

3Finds shortest paths between ALL pairs of nodes

Practice Problems

1Find the City With the Smallest Number of Neighbors at a Threshold Distance
2Evaluate Division
3Minimum Cost to Convert String I

About the Shortest Path Pattern

Find the minimum cost path between nodes. The right algorithm depends on the graph: unweighted → BFS, non-negative weights → Dijkstra, negative weights → Bellman-Ford, all-pairs → Floyd-Warshall.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Why must the intermediate node k be the outermost loop?

The DP builds answers in layers: paths using intermediates {1..k} depend on complete answers for {1..k-1}. Putting k inside i or j mixes layers, reading entries that have not yet been allowed to route through earlier intermediates, and produces wrong distances on some graphs.

When is Floyd-Warshall the right choice over repeated Dijkstra?

When you need distances between all pairs and V is small (roughly V up to 400-500) or the graph is dense, where O(V³) is comparable to V runs of Dijkstra anyway. It is also the pragmatic pick when negative edges rule out Dijkstra and the graph is small.