Floyd-Warshall

Floyd-Warshall Algorithm

Introduction

Given a directed or undirected weighted graph $G$ with $n$ vertices. The task is to find the length of the shortest path $d_{xy}$ between each pair of vertices $x$ and $y$ . The graph may have edges with negative weights, but there are no negative weight cycles.

This algorithm can also be used to determine the presence of negative cycles. The graph has a negative cycle if at the end of the algorithm the distance from vertex to itself is negative.

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

ATCODERD. joisino's travel

ATCODERD. Shortest Path Queries 2

ATCODERD. Candidates of No Shortest Paths

ATCODERD. Wall

ATCODERE. Travel by Car

ATCODERE. Development

CODEFORCESGreg and Graph

Rating: 1700

CODEFORCESString Problem

Rating: 1800

CODEFORCESRoads in Berland

Rating: 1900

CODEFORCESCryptography

v

Algorithm

The main idea of the algorithm is to break the process of finding the shortest path between any two vertices into several iterative stages.

Before the $k$ -th stage ( $k = 1 \ldots n$ ), $d[x][y]$ for any vertices $x$ and $y$ stores the length of the shortest path from vertex $x$ to vertex $y$ , which contains only the vertices $\{1, 2, ..., k-1\}$ as intermediate vertices of the path.

It is easy to verify that this property holds for the first phase. For $k = 0$ , we can fill the matrix $d[x][y] = w_{xy}$ if there is an edge from $x$ to $y$ with weight $w_{xy}$ and $d[x][y] = \infty$ if the edge does not exist. In practice, $\infty$ will have some large value.

Now suppose we are at the $k$ -th phase and want to compute the matrix $d[ ][ ]$ such that it satisfies the requirements for the $(k + 1)$ -th stage. We need to fix the distances for some pairs of vertices $(x, y)$ . Here, two fundamentally different cases are possible:

The shortest path from vertex $x$ to vertex $y$ with intermediate vertices from the set $\{1, 2, \dots, k\}$ coincides with the shortest path with intermediate vertices from the set $\{1, 2, \dots, k-1\}$ . In this case, $d[x][y]$ does not change during the transition.
The shortest path with intermediate vertices from $\{1, 2, \dots, k\}$ is shorter. This means that the new, shorter path goes through vertex $k$ . This implies that we can break the shortest path between $x$ and $y$ into two paths: the path from $x$ to $k$ , and the path from to . Clearly, both of these paths use only intermediate vertices from the set and are shortest in this sense. Therefore, we have already computed the lengths of these paths earlier, and we can compute the length of the shortest path between and as .

Thus, we have the formula for the $k$ -th phase:

$d_{\text{new}}[x][y] = \min(d[x][y], d[x][k] + d[k][y])$

Consequently, all that is required at the $k$ -th stage is to iterate through all pairs of vertices and recalculate the length of the shortest path between them. As a result, after the $n$ -th stage, the value of $d[x][y]$ in the distance matrix is the length of the shortest path between $x$ and $y$ , or it equals $\infty$ if there is no path between vertices $x$ and $y$ .

Asymptotic complexity $O(N^3)$

Problems

k

y

\{1, 2, \dots, k-1\}

x

y

d[x][k] + d[k][y]

for (int h = 1; h <= n; h++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = min(d[i][j], d[i][h] + d[h][j]);    
        }
    }
}