Floyd - 1#974

Floyd - 1 (Editorial)

El problema requiere encontrar las distancias más cortas entre todos los pares de vértices. Este es un problema clásico que se resuelve mediante el algoritmo de Floyd — Warshall. El algoritmo se basa en programación dinámica y funciona correctamente con pesos de aristas negativos, siempre que el grafo no contenga ciclos de peso negativo. Esta condición está garantizada en el problema.

Idea del algoritmo. Numeremos los vértices del $1$ al $n$ . Denotemos por $d_{k} [i] [j]$ d_k[i][j] la longitud del camino más corto desde el vértice $i$ hasta el vértice $j$ cuyos vértices intermedios pertenecen todos al conjunto ${1, 2, \dots, k}$ \{1, 2, \ldots, k\}. Para $k = 0$ k = 0 no hay vértices intermedios, por lo que $d_{0} [i] [j]$ d_0[i][j] es igual al peso de la arista $i \to j$ i \to j, es decir, coincide con la matriz de adyacencia.

Consideremos el camino más corto de $i$ a $j$ cuyos vértices intermedios se encuentran entre ${1, \dots, k}$ \{1, \ldots, k\}. Son posibles dos casos:

el camino no pasa por el vértice $k$ . Entonces su longitud es igual a $d_{k - 1} [i] [j]$ d_{k-1}[i][j];
el camino pasa por el vértice $k$ . Dado que no hay ciclos de peso negativo, es óptimo visitar el vértice $k$ exactamente una vez. El camino se divide en dos partes: de $i$ a $k$ y de $k$ a $j$ . Los vértices intermedios de ambas partes se encuentran entre ${1, \dots, k - 1}$ \{1, \ldots, k - 1\}, por lo que la longitud del camino es igual a $d_{k - 1} [i] [k] + d_{k - 1} [k] [j]$ d_{k-1}[i][k] + d_{k-1}[k][j].

Eligiendo la mejor de las dos opciones, obtenemos la recurrencia:

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])

La matriz $d_{n}$ d_n contiene las distancias más cortas requeridas, ya que cualquier vértice del grafo puede ser intermedio en ella.

Cálculo en una sola matriz. No es necesario almacenar todas las matrices $d_{0}, d_{1}, \dots, d_{n}$ d_0, d_1, \ldots, d_n: todos los cálculos se pueden realizar directamente en la matriz de adyacencia $g$ . En efecto, en el paso $k$ los valores $g [i] [k]$ g[i][k] y $g [k] [j]$ g[k][j] no cambian, ya que $g [k] [k] = 0$ g[k][k] = 0. Por ejemplo, $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]. Por lo tanto, no importa si los demás elementos de la matriz ya han sido actualizados en el paso actual.

Es importante que el bucle sobre el vértice intermedio $k$ sea el más externo: para cuando se procesa el vértice $k$ , ya deben estar calculadas todas las distancias con vértices intermedios de ${1, \dots, k - 1}$ \{1, \ldots, k - 1\}.

Complejidad. El algoritmo consiste en tres bucles anidados de $n$ iteraciones cada uno, por lo que su tiempo de ejecución es $O (n^{3})$ O(n^3). Para $n \leq 100$ n \le 100 esto equivale a aproximadamente $1 0^{6}$ 10^6 operaciones.

Ejemplo

El grafo dado en el ejemplo se muestra a continuación. El grafo es completo, pero las aristas de peso $100$ no se muestran en la figura: como veremos más adelante, ninguna de ellas pertenece a ningún camino más corto.

Simulemos el algoritmo. La matriz inicial $g$ coincide con la matriz de adyacencia:

	$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}. Los caminos desde el vértice $4$ se vuelven más cortos a través del vértice $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 y $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}. A través del vértice $2$ , los siguientes caminos se vuelven más cortos: $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 y $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}. Pasar por el vértice $3$ no acorta ningún camino. Por ejemplo, $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}. A través del vértice $4$ , los caminos hacia los vértices $1$ y $2$ se vuelven más cortos: $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 y $g [3] [2] = g [3] [4] + g [4] [2] = 7 + 9 = 16$ g[3][2] = g[3][4] + g[4][2] = 7 + 9 = 16.

Observemos la última actualización. El valor $g [4] [2] = 9$ g[4][2] = 9 se obtuvo en el paso $k = 1$ k = 1 y corresponde al camino $4 \to 1 \to 2$ 4 \to 1 \to 2. Por lo tanto, $g [3] [2] = 16$ g[3][2] = 16 corresponde al camino $3 \to 4 \to 1 \to 2$ 3 \to 4 \to 1 \to 2, que tiene dos vértices intermedios.

La matriz final de distancias más cortas coincide con la respuesta del ejemplo:

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

Implementación del algoritmo

Almacenemos la matriz de adyacencia del grafo en el arreglo $g$ .

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

La función floyd implementa el algoritmo de Floyd — Warshall.

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++

La parte principal del programa. Leamos el grafo de entrada.

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

Ejecutemos el algoritmo de Floyd — Warshall.

floyd();

Imprimamos la matriz de las distancias más cortas entre todos los pares de vértices.

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

Implementación en Java

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

Implementación en Python

La función floyd implementa el algoritmo de Floyd — Warshall.

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]

La parte principal del programa. Leamos el grafo de entrada.

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

Ejecutemos el algoritmo de Floyd — Warshall.

floyd()

Imprimamos la matriz de las distancias más cortas entre todos los pares de vértices.

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