Floyd - 1#974

Floyd - 1 (Editorial)

The problem requires finding the shortest distances between all pairs of vertices. This is a classical problem solved by the Floyd — Warshall algorithm. The algorithm is based on dynamic programming and works correctly with negative edge weights, provided that the graph contains no negative-weight cycles. This condition is guaranteed in the problem.

Idea of the algorithm. Number the vertices from $1$ to $n$ . Denote by $d_{k} [i] [j]$ d_k[i][j] the length of the shortest path from vertex $i$ to vertex $j$ all of whose intermediate vertices belong to the set ${1, 2, \dots, k}$ \{1, 2, \ldots, k\}. For $k = 0$ k = 0 there are no intermediate vertices, so $d_{0} [i] [j]$ d_0[i][j] equals the weight of the edge $i \to j$ i \to j, that is, it coincides with the adjacency matrix.

Consider the shortest path from $i$ to $j$ whose intermediate vertices lie among ${1, \dots, k}$ \{1, \ldots, k\}. Two cases are possible:

the path does not pass through vertex $k$ . Then its length equals $d_{k - 1} [i] [j]$ d_{k-1}[i][j];
the path passes through vertex $k$ . Since there are no negative-weight cycles, it is optimal to visit vertex $k$ exactly once. The path splits into two parts: from $i$ to $k$ and from $k$ to $j$ . The intermediate vertices of both parts lie among ${1, \dots, k - 1}$ \{1, \ldots, k - 1\}, so the length of the path equals $d_{k - 1} [i] [k] + d_{k - 1} [k] [j]$ d_{k-1}[i][k] + d_{k-1}[k][j].

Choosing the better of the two options, we obtain the recurrence:

d_{k} [i] [j] = min (d_{k - 1} [i] [j], d_{k - 1} [i] [k] + d_{k - 1} [k] [j])

d_k[i][j] = \min(d_{k-1}[i][j], d_{k-1}[i][k] + d_{k-1}[k][j])

The matrix $d_{n}$ d_n contains the required shortest distances, since any vertex of the graph may be intermediate in it.

Computing in a single matrix. There is no need to store all the matrices $d_{0}, d_{1}, \dots, d_{n}$ d_0, d_1, \ldots, d_n: all computations can be performed directly in the adjacency matrix $g$ . Indeed, at step $k$ the values $g [i] [k]$ g[i][k] and $g [k] [j]$ g[k][j] do not change, since $g [k] [k] = 0$ g[k][k] = 0. For example, $g [i] [k] = min (g [i] [k], g [i] [k] + g [k] [k]) = g [i] [k]$ g[i][k] = \min(g[i][k], g[i][k] + g[k][k]) = g[i][k]. Therefore, it does not matter whether the other elements of the matrix have already been updated at the current step.

It is important that the loop over the intermediate vertex $k$ is the outer one: by the time vertex $k$ is processed, all distances with intermediate vertices from ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} must already be computed.

Complexity. The algorithm consists of three nested loops of $n$ iterations each, so its running time is $O (n^{3})$ O(n^3). For $n \leq 100$ n \le 100 this is about $1 0^{6}$ 10^6 operations.

Example

The graph given in the example is shown below. The graph is complete, but the edges of weight $100$ are not shown in the figure: as we will see below, none of them belongs to any shortest path.

Let us simulate the algorithm. The initial matrix $g$ coincides with the adjacency matrix:

	$1$	$2$	$3$	$4$
$1$	$0$	$5$	$9$	$100$
$2$	$100$	$0$	$2$	$8$
$3$	$100$	$100$	$0$	$7$
$4$	$4$	$100$	$100$	$0$

$k = 1$ \boldsymbol{k = 1}. Paths from vertex $4$ become shorter via vertex $1$ : $g [4] [2] = g [4] [1] + g [1] [2] = 4 + 5 = 9$ g[4][2] = g[4][1] + g[1][2] = 4 + 5 = 9 and $g [4] [3] = g [4] [1] + g [1] [3] = 4 + 9 = 13$ g[4][3] = g[4][1] + g[1][3] = 4 + 9 = 13.

$k = 2$ \boldsymbol{k = 2}. Via vertex $2$ , the following paths become shorter: $g [1] [3] = g [1] [2] + g [2] [3] = 5 + 2 = 7$ g[1][3] = g[1][2] + g[2][3] = 5 + 2 = 7, $g [1] [4] = g [1] [2] + g [2] [4] = 5 + 8 = 13$ g[1][4] = g[1][2] + g[2][4] = 5 + 8 = 13 and $g [4] [3] = g [4] [2] + g [2] [3] = 9 + 2 = 11$ g[4][3] = g[4][2] + g[2][3] = 9 + 2 = 11.

$k = 3$ \boldsymbol{k = 3}. Passing through vertex $3$ does not shorten any path. For example, $g [1] [3] + g [3] [4] = 7 + 7 = 14 > g [1] [4] = 13$ g[1][3] + g[3][4] = 7 + 7 = 14 > g[1][4] = 13.

$k = 4$ \boldsymbol{k = 4}. Via vertex $4$ , paths to vertices $1$ and $2$ become shorter: $g [2] [1] = g [2] [4] + g [4] [1] = 8 + 4 = 12$ g[2][1] = g[2][4] + g[4][1] = 8 + 4 = 12, $g [3] [1] = g [3] [4] + g [4] [1] = 7 + 4 = 11$ g[3][1] = g[3][4] + g[4][1] = 7 + 4 = 11 and $g [3] [2] = g [3] [4] + g [4] [2] = 7 + 9 = 16$ g[3][2] = g[3][4] + g[4][2] = 7 + 9 = 16.

Note the last update. The value $g [4] [2] = 9$ g[4][2] = 9 was obtained at step $k = 1$ k = 1 and corresponds to the path $4 \to 1 \to 2$ 4 \to 1 \to 2. Therefore, $g [3] [2] = 16$ g[3][2] = 16 corresponds to the path $3 \to 4 \to 1 \to 2$ 3 \to 4 \to 1 \to 2, which has two intermediate vertices.

The final shortest distance matrix coincides with the answer from the example:

	$1$	$2$	$3$	$4$
$1$	$0$	$5$	$7$	$13$
$2$	$12$	$0$	$2$	$8$
$3$	$11$	$16$	$0$	$7$
$4$	$4$	$9$	$11$	$0$

Algorithm implementation

Store the adjacency matrix of the graph in the array $g$ .

#define MAX 101
int g[MAX][MAX];

The floyd function implements the Floyd — Warshall algorithm.

void floyd(void)
{
  int i, j, k;
  for(k = 0; k < n; k++)
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if (g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j];
}

C++

The main part of the program. Read the input graph.

scanf("%d",&n);
for(i = 0; i <  n; i++)
for(j = 0; j <  n; j++)
  scanf("%d",&g[i][j]);

Run the Floyd — Warshall algorithm.

floyd();

Print the matrix of the shortest distances between all pairs of vertices.

for(i = 0; i <  n; i++)
{
  for(j = 0; j <  n; j++)
    printf("%d ",g[i][j]);
  printf("\n");
}

Java implementation

import java.util.*;

public class Main 
{
  static int g[][];
  static int n;
  
  static void floyd()
  {
    for(int k = 0; k < n; k++)
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      if (g[i][k] + g[k][j] < g[i][j]) 
        g[i][j] = g[i][k] + g[k][j];
  }
  
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);	  
    n = con.nextInt();
    g = new int[n][n];

    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      g[i][j] = con.nextInt();

    floyd();

    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
    	  System.out.print(g[i][j] + " ");
      System.out.println();
    }
    con.close();
  }
}

Java

Python implementation

The floyd function implements the Floyd — Warshall algorithm.

def floyd():
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if g[i][k] + g[k][j] < g[i][j]:
           g[i][j] = g[i][k] + g[k][j]

The main part of the program. Read the input graph.

n = int(input())
g = [[] for _ in range(n)]
for i in range(n):
  g[i] = list(map(int, input().split()))

Run the Floyd — Warshall algorithm.

floyd()

Print the matrix of the shortest distances between all pairs of vertices.

for i in range(n):
  print(*g[i])