Floyd–Warshall algorithm

Definition

Let $G$ be a finite directed graph with vertex set $\set{1, \dots, n}$ and edge weights $w(i, j) \in \R$. Assume that $G$ has no cycle of negative total weight. The Floyd–Warshall algorithm is the algorithm that computes numbers $d_k(i, j)$ for $k = 0, 1, \dots, n$ as follows.

1. $d_0(i, i) = 0$; $d_0(i, j) = w(i, j)$ if $i \ne j$ and $(i, j)$ is an edge; and $d_0(i, j) = \infty$ otherwise.
2. For $k \ge 1$, $d_k(i, j) = \min\bigl(d_{k-1}(i, j),\ d_{k-1}(i, k) + d_{k-1}(k, j)\bigr)$.

It returns $d_n(i, j)$ for all pairs $(i, j)$. Here $d_k(i, j)$ is the least weight of a directed path from $i$ to $j$ whose intermediate vertices all lie in $\set{1, \dots, k}$. So $d_n(i, j)$ is the shortest path distance from $i$ to $j$.