# Floyd-Warshall Algorithm **An algorithm for finding the [[Shortest Path Problem|shortest path]] between any pairs of vertices in a real [[Graph#Weighted graph|weighted graph]] with no negative [[Cycle|cycles]].** ![[Floyd-WarshallAlgorithm.svg|600]] *Floyd-Warshall algorithm on a graph; each iteration of $k$ tries to find shorter paths between all other vertices through $v_{k}$* ***Worst-case [[time complexity]]:*** $O(V^{3})$ > [!Example] Algorithm > 1. Initialise a 2D array `dist[u][v]` of shortest distances between every vertex. > 2. For every edge `(u, v)` with weight `w(u, w)`, `dist[v][w] = w(u, w)`. > 3. For every vertex `v`, `dist[v][v] = 0` > 4. For `i = 1` to `|V|`, > - For `j = 1` to `|V|`, > - For `k = 1` to `|V|`, > 1. If `dist[j][k] > dist[j][i] + dist[i][k]`, > - `dist[j][k] = dist[j][i] + dist[i][k]` The *Floyd-Warshall algorithm* is a [[dynamic programming]] algorithm that works by initially noting the distances along single edge paths and then considering paths between pairs of vertices through each of the vertices. The time complexity derives from the need to calculate the distance between all possible pairs of vertices, which is $V^{2}$, for paths through $V$ vertices. As a dynamic programming algorithm it can also be specified with more detail of the subproblems and recurrence relation. > [!Dynamic programming specification] > ***Subproblems*** > The subproblem $P(i, j, k)$ for all $0\le i\le |V|$, $1 \le j$, and $k\le |V|$ is the problem of determining $\text{opt}(i, j, k)$, the weight of the shortest path from $v_{j}$ to $v_{k}$ using only $v_{1},\dots,v_{i}$ along the path. > > ***Base cases*** > The base cases are > $ > \text{opt}(0, j, k)= > \begin{cases} > 0,\quad &\text{if } j = k \\ > w(j, k),\quad &\text{if }(v_{j}, v_{k})\in E \\ > \infty, \quad &\text{otherwise} > \end{cases} > $ > > ***Recurrence relation*** > For all $1\le i,j,k\le n$, > $\text{opt}(i,j,k)=\min[\text{opt}(i-1,j,k),\text{opt}(i-1,j,i)+\text{opt}(i-1,i, k)]$ > > ***Order of computation*** > The order of computation is in increasing order of $i$. > > ***Overall solution*** > The overall solution is the table of values $\text{opt}(|V|, j, k)$ for all pairs of vertices $v_{j}, v_{k}$.