Floyd-Warshall Algorithm — Definition, Formula & Examples

The Floyd-Warshall algorithm is a dynamic programming method that computes the shortest path between every pair of vertices in a weighted graph. It works on graphs with positive or negative edge weights, as long as there are no negative-weight cycles.

Given a weighted directed graph $G = (V, E)$ with $n = |V|$ vertices, the Floyd-Warshall algorithm constructs a sequence of matrices $D^{(0)}, D^{(1)}, \ldots, D^{(n)}$ where $D^{(k)}[i][j]$ represents the weight of the shortest path from vertex $i$ to vertex $j$ using only vertices $\{1, 2, \ldots, k\}$ as intermediate nodes. The final matrix $D^{(n)}$ contains all-pairs shortest path distances.

Key Formula

D^{(k)}[i][j] = \min\!\left(D^{(k-1)}[i][j],\; D^{(k-1)}[i][k] + D^{(k-1)}[k][j]\right)

Where:

$D^{(k)}[i][j]$ = Shortest distance from vertex i to vertex j using only vertices 1 through k as intermediates
$k$ = Current intermediate vertex being considered (ranges from 1 to n)
$i, j$ = Source and destination vertices

How It Works

Start by initializing a distance matrix

D

where

D[i][j]

equals the edge weight from

i

j

if that edge exists,

0

i = j

, and

\infty

otherwise. Then iterate through every possible intermediate vertex

k

from

1

n

. For each pair

(i, j)

, check whether routing through

k

yields a shorter path than the current best. If

D[i][k] + D[k][j] < D[i][j]

, update

D[i][j]

. After all

n

iterations, the matrix holds the shortest distances between all pairs. The algorithm runs in

O(n^3)

time and

O(n^2)

space.

Worked Example

Problem: Find all-pairs shortest paths for a 3-vertex graph with edges: 1→2 (weight 4), 1→3 (weight 11), 2→3 (weight 2).

Initialize D⁽⁰⁾: Set up the distance matrix from the given edge weights. Missing edges get infinity.

D^{(0)} = \begin{pmatrix} 0 & 4 & 11 \\ \infty & 0 & 2 \\ \infty & \infty & 0 \end{pmatrix}

k = 1 (intermediate vertex 1): Check if routing through vertex 1 improves any path. For D[2][3]: min(2, ∞ + 4) = 2. For D[3][2]: min(∞, ∞ + 4) = ∞. No changes occur.

D^{(1)} = D^{(0)}

k = 2 (intermediate vertex 2): Check if routing through vertex 2 improves any path. For D[1][3]: min(11, 4 + 2) = 6. The path 1→2→3 is shorter than the direct edge 1→3.

D^{(2)}[1][3] = \min(11,\; 4 + 2) = 6

k = 3 (intermediate vertex 3): Check if routing through vertex 3 improves any remaining path. No further improvements are found.

D^{(3)} = \begin{pmatrix} 0 & 4 & 6 \\ \infty & 0 & 2 \\ \infty & \infty & 0 \end{pmatrix}

Answer: The shortest distances are: 1→2 = 4, 1→3 = 6 (via vertex 2), 2→3 = 2. All other pairs have no connecting path (∞).

Why It Matters

Floyd-Warshall is a standard algorithm in computer science courses on data structures and algorithms. It appears in network routing protocols, geographic information systems, and any application that needs pairwise distances — such as finding the diameter of a graph or detecting negative cycles.

Common Mistakes

Mistake: Placing the k-loop (intermediate vertex) inside the i-j loops instead of as the outermost loop.

Correction: The loop order must be k (outermost), then i, then j. Swapping this order means the algorithm considers intermediate vertices before their sub-paths are fully computed, producing incorrect results.