Floyd - 1#974

Floyd - 1 (Editoriale)

Il problema richiede di trovare le distanze più brevi tra tutte le coppie di vertici. Si tratta di un problema classico risolto dall'algoritmo di Floyd — Warshall. L'algoritmo si basa sulla programmazione dinamica e funziona correttamente anche con pesi negativi sugli archi, a condizione che il grafo non contenga cicli di peso negativo. Questa condizione è garantita nel problema.

Idea dell'algoritmo. Numeriamo i vertici da $1$ a $n$ . Indichiamo con $d_{k} [i] [j]$ d_k[i][j] la lunghezza del cammino più breve dal vertice $i$ al vertice $j$ i cui vertici intermedi appartengono tutti all'insieme ${1, 2, \dots, k}$ \{1, 2, \ldots, k\}. Per $k = 0$ k = 0 non ci sono vertici intermedi, quindi $d_{0} [i] [j]$ d_0[i][j] è uguale al peso dell'arco $i \to j$ i \to j, cioè coincide con la matrice di adiacenza.

Consideriamo il cammino più breve da $i$ a $j$ i cui vertici intermedi si trovano tra ${1, \dots, k}$ \{1, \ldots, k\}. Sono possibili due casi:

il cammino non passa per il vertice $k$ . In tal caso la sua lunghezza è uguale a $d_{k - 1} [i] [j]$ d_{k-1}[i][j];
il cammino passa per il vertice $k$ . Poiché non esistono cicli di peso negativo, è ottimale visitare il vertice $k$ esattamente una volta. Il cammino si divide in due parti: da $i$ a $k$ e da $k$ a $j$ . I vertici intermedi di entrambe le parti si trovano tra ${1, \dots, k - 1}$ \{1, \ldots, k - 1\}, quindi la lunghezza del cammino è uguale a $d_{k - 1} [i] [k] + d_{k - 1} [k] [j]$ d_{k-1}[i][k] + d_{k-1}[k][j].

Scegliendo la migliore tra le due opzioni, otteniamo la relazione di ricorrenza:

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 matrice $d_{n}$ d_n contiene le distanze più brevi richieste, poiché in essa qualsiasi vertice del grafo può essere intermedio.

Calcolo in un'unica matrice. Non è necessario memorizzare tutte le matrici $d_{0}, d_{1}, \dots, d_{n}$ d_0, d_1, \ldots, d_n: tutti i calcoli possono essere eseguiti direttamente nella matrice di adiacenza $g$ . Infatti, al passo $k$ i valori $g [i] [k]$ g[i][k] e $g [k] [j]$ g[k][j] non cambiano, poiché $g [k] [k] = 0$ g[k][k] = 0. Ad esempio, $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]. Pertanto, non importa se gli altri elementi della matrice sono già stati aggiornati nel passo corrente.

È importante che il ciclo sul vertice intermedio $k$ sia quello più esterno: quando si elabora il vertice $k$ , tutte le distanze con vertici intermedi appartenenti a ${1, \dots, k - 1}$ \{1, \ldots, k - 1\} devono essere già state calcolate.

Complessità. L'algoritmo è costituito da tre cicli annidati di $n$ iterazioni ciascuno, quindi il suo tempo di esecuzione è $O (n^{3})$ O(n^3). Per $n \leq 100$ n \le 100 si tratta di circa $1 0^{6}$ 10^6 operazioni.

Esempio

Il grafo riportato nell'esempio è mostrato di seguito. Il grafo è completo, ma gli archi di peso $100$ non sono mostrati nella figura: come vedremo più avanti, nessuno di essi appartiene a un cammino più breve.

Simuliamo l'algoritmo. La matrice iniziale $g$ coincide con la matrice di adiacenza:

	$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}. I cammini dal vertice $4$ diventano più brevi passando per il vertice $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 e $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}. Passando per il vertice $2$ , i seguenti cammini diventano più brevi: $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 e $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}. Passare per il vertice $3$ non accorcia nessun cammino. Ad esempio, $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}. Passando per il vertice $4$ , i cammini verso i vertici $1$ e $2$ diventano più brevi: $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 e $g [3] [2] = g [3] [4] + g [4] [2] = 7 + 9 = 16$ g[3][2] = g[3][4] + g[4][2] = 7 + 9 = 16.

Osserviamo l'ultimo aggiornamento. Il valore $g [4] [2] = 9$ g[4][2] = 9 è stato ottenuto al passo $k = 1$ k = 1 e corrisponde al cammino $4 \to 1 \to 2$ 4 \to 1 \to 2. Pertanto, $g [3] [2] = 16$ g[3][2] = 16 corrisponde al cammino $3 \to 4 \to 1 \to 2$ 3 \to 4 \to 1 \to 2, che ha due vertici intermedi.

La matrice finale delle distanze più brevi coincide con la risposta dell'esempio:

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

Implementazione dell'algoritmo

Memorizziamo la matrice di adiacenza del grafo nell'array $g$ .

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

La funzione floyd implementa l'algoritmo di 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 principale del programma. Leggiamo il grafo in input.

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

Eseguiamo l'algoritmo di Floyd — Warshall.

floyd();

Stampiamo la matrice delle distanze più brevi tra tutte le coppie di vertici.

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

Implementazione in 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

Implementazione in Python

La funzione floyd implementa l'algoritmo di 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 principale del programma. Leggiamo il grafo in input.

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

Eseguiamo l'algoritmo di Floyd — Warshall.

floyd()

Stampiamo la matrice delle distanze più brevi tra tutte le coppie di vertici.

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