logo

TechCodeview

Algoritmo di Floyd Warshall

IL Algoritmo di Floyd-Warshall , dal nome dei suoi creatori Robert Floyd e Stephen Warshall , è un algoritmo fondamentale nell'informatica e nella teoria dei grafi. Viene utilizzato per trovare i percorsi più brevi tra tutte le coppie di nodi in un grafico ponderato. Questo algoritmo è altamente efficiente e può gestire i grafici con entrambi positivo e n pesi dei bordi negativi , rendendolo uno strumento versatile per risolvere un'ampia gamma di problemi di rete e connettività.

Tabella dei contenuti

Banner dell'algoritmo Floyd-Warshall



Algoritmo di Floyd Warshall:

IL Algoritmo di Floyd Warshall è un algoritmo del percorso più breve per tutte le coppie, a differenza di Dijkstra E Il fattorino Ford che sono algoritmi di percorso più breve a sorgente singola. Questo algoritmo funziona sia per il dirette E ponderato non diretto grafici. Ma non funziona per i grafici con cicli negativi (dove la somma degli archi in un ciclo è negativa). Segue Programmazione dinamica approccio per verificare ogni possibile percorso che passa attraverso ogni possibile nodo al fine di calcolare la distanza più breve tra ogni coppia di nodi.

connettere il database java

Idea dietro l’algoritmo di Floyd Warshall:

Supponiamo di avere un grafico G[][] con IN vertici da 1 A N . Ora dobbiamo valutare a matricePercorso più breve[][] dov 'è hortestPathMatrix[i][j] rappresenta il percorso più breve tra i vertici io E J .

Ovviamente il percorso più breve in mezzo io A J ne avrà alcuni K numero di nodi intermedi. L'idea alla base dell'algoritmo di Floyd Warshall è di trattare ogni singolo vertice da 1 A N come nodo intermedio uno per uno.

La figura seguente mostra la proprietà della sottostruttura ottimale sopra nell'algoritmo di Floyd Warshall:

Algoritmo dell'algoritmo di Floyd Warshall:

  • Inizializzare la matrice della soluzione come la matrice del grafico di input come primo passaggio.
  • Quindi aggiorna la matrice della soluzione considerando tutti i vertici come un vertice intermedio.
  • L'idea è di scegliere tutti i vertici uno per uno e aggiornare tutti i percorsi più brevi che includono il vertice selezionato come vertice intermedio nel percorso più breve.
  • Quando scegliamo il numero del vertice K come vertice intermedio abbiamo già considerato i vertici {0, 1, 2, ..k-1} come vertici intermedi.
  • Per ogni coppia (io, j) dei vertici sorgente e destinazione rispettivamente, ci sono due casi possibili.
    • K non è un vertice intermedio nel percorso più breve da io A J . Manteniamo il valore di dist[i][j] così com'è.
    • K è un vertice intermedio nel percorso più breve da io A J . Aggiorniamo il valore di dist[i][j] COME dist[i][k] + dist[k][j], Se dist[i][j]> dist[i][k] + dist[k][j]

Pseudo-codice dell'algoritmo di Floyd Warshall:>

Per k = 0 fino a n – 1
Per i = 0 fino a n – 1
Per j = 0 fino a n – 1
Distanza[i, j] = min(Distanza[i, j], Distanza[i, k] + Distanza[k, j])

dove i = nodo sorgente, j = nodo di destinazione, k = nodo intermedio

Illustrazione dell'algoritmo di Floyd Warshall:

Supponiamo di avere un grafico come mostrato nell'immagine:

convenzione sui nomi java
dryRun1drawio

Passo 1 : Inizializza la matrice Distance[][] utilizzando il grafico di input in modo tale che Distance[i][j]= peso del bordo da io A J , anche Distanza[i][j] = Infinito se non vi è alcun bordo da io A J.

step1drawio

Passo 2 : Trattare il nodo UN come nodo intermedio e calcola la Distanza[][] per ogni coppia di nodi {i,j} utilizzando la formula:

= Distanza[i][j] = minimo (Distanza[i][j], (Distanza da i a UN ) + (Distanza da UN a j ))
= Distanza[i][j] = minimo (Distanza[i][j], Distanza[i][ UN ] + Distanza[ UN ][J])

step2drawio

Passaggio 3 : Trattare il nodo B come nodo intermedio e calcola la Distanza[][] per ogni coppia di nodi {i,j} utilizzando la formula:

= Distanza[i][j] = minimo (Distanza[i][j], (Distanza da i a B ) + (Distanza da B a j ))
= Distanza[i][j] = minimo (Distanza[i][j], Distanza[i][ B ] + Distanza[ B ][J])

step3drawio

Passaggio 4 : Trattare il nodo C come nodo intermedio e calcola la Distanza[][] per ogni coppia di nodi {i,j} utilizzando la formula:

= Distanza[i][j] = minimo (Distanza[i][j], (Distanza da i a C ) + (Distanza da C a j ))
= Distanza[i][j] = minimo (Distanza[i][j], Distanza[i][ C ] + Distanza[ C ][J])

step4dravio

Passaggio 5 : Trattare il nodo D come nodo intermedio e calcola la Distanza[][] per ogni coppia di nodi {i,j} utilizzando la formula:

Ubuntu build essenziale

= Distanza[i][j] = minimo (Distanza[i][j], (Distanza da i a D ) + (Distanza da D a j ))
= Distanza[i][j] = minimo (Distanza[i][j], Distanza[i][ D ] + Distanza[ D ][J])

step5drawio

Passaggio 6 : Trattare il nodo E come nodo intermedio e calcola la Distanza[][] per ogni coppia di nodi {i,j} utilizzando la formula:

= Distanza[i][j] = minimo (Distanza[i][j], (Distanza da i a E ) + (Distanza da E a j ))
= Distanza[i][j] = minimo (Distanza[i][j], Distanza[i][ E ] + Distanza[ E ][J])

step6drawio

Passaggio 7 : Poiché tutti i nodi sono stati trattati come nodi intermedi, ora possiamo restituire la matrice Distanza[][] aggiornata come matrice di risposta.

step7drawio
Pratica consigliata Provalo!

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++ 
// C++ Program for Floyd Warshall Algorithm #include  using namespace std; // Number of vertices in the graph #define V 4 /* Define Infinite as a large enough value.This value will be used for vertices not connected to each other */ #define INF 99999 // A function to print the solution matrix void printSolution(int dist[][V]); // Solves the all-pairs shortest path // problem using Floyd Warshall algorithm void floydWarshall(int dist[][V]) {  int i, j, k;  /* Add all vertices one by one to  the set of intermediate vertices.  --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici tali che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.  ----> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} */ for (k = 0; k< V; k++) {  // Pick all vertices as source one by one  for (i = 0; i < V; i++) {  // Pick all vertices as destination for the  // above picked source  for (j = 0; j < V; j++) {  // If vertex k is on the shortest path from  // i to j, then update the value of  // dist[i][j]  if (dist[i][j]>(dist[i][k] + dist[k][j]) && (dist[k][j] != INF && dist[i][k] != INF)) dist[i][j] = dist[i][k] + dist[k][j];  } } } // Stampa la matrice della distanza più breve printSolution(dist); } /* Una funzione di utilità per stampare la soluzione */ void printSolution(int dist[][V]) { cout<< 'The following matrix shows the shortest '  'distances'  ' between every pair of vertices 
';  for (int i = 0; i < V; i++) {  for (int j = 0; j < V; j++) {  if (dist[i][j] == INF)  cout << 'INF'  << ' ';  else  cout << dist[i][j] << ' ';  }  cout << endl;  } } // Driver's code int main() {  /* Let us create the following weighted graph  10  (0)------->(3) | /|5 | |  | | 1 |/ |  (1)------->(2) 3 */ int grafico[V][V] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, {INF, INF, INF, 0 } };  // Chiamata di funzione floydWarshall(graph);  restituire 0; } // Questo codice è un contributo di Mythri J L>
C 
// C Program for Floyd Warshall Algorithm #include  // Number of vertices in the graph #define V 4 /* Define Infinite as a large enough  value. This value will be used  for vertices not connected to each other */ #define INF 99999 // A function to print the solution matrix void printSolution(int dist[][V]); // Solves the all-pairs shortest path // problem using Floyd Warshall algorithm void floydWarshall(int dist[][V]) {  int i, j, k;  /* Add all vertices one by one to  the set of intermediate vertices.  --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici tali che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.  ----> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} */ for (k = 0; k< V; k++) {  // Pick all vertices as source one by one  for (i = 0; i < V; i++) {  // Pick all vertices as destination for the  // above picked source  for (j = 0; j < V; j++) {  // If vertex k is on the shortest path from  // i to j, then update the value of  // dist[i][j]  if (dist[i][k] + dist[k][j] < dist[i][j])  dist[i][j] = dist[i][k] + dist[k][j];  }  }  }  // Print the shortest distance matrix  printSolution(dist); } /* A utility function to print solution */ void printSolution(int dist[][V]) {  printf(  'The following matrix shows the shortest distances'  ' between every pair of vertices 
');  for (int i = 0; i < V; i++) {  for (int j = 0; j < V; j++) {  if (dist[i][j] == INF)  printf('%7s', 'INF');  else  printf('%7d', dist[i][j]);  }  printf('
');  } } // driver's code int main() {  /* Let us create the following weighted graph  10  (0)------->(3) | /|5 | |  | | 1 |/ |  (1)------->(2) 3 */ int grafico[V][V] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, {INF, INF, INF, 0 } };  // Chiamata di funzione floydWarshall(graph);  restituire 0; }>
Giava 
// Java program for Floyd Warshall All Pairs Shortest // Path algorithm. import java.io.*; import java.lang.*; import java.util.*; class AllPairShortestPath {  final static int INF = 99999, V = 4;  void floydWarshall(int dist[][])  {  int i, j, k;  /* Add all vertices one by one  to the set of intermediate  vertices.  --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici tali che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.  ----> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} */ for (k = 0; k< V; k++) {  // Pick all vertices as source one by one  for (i = 0; i < V; i++) {  // Pick all vertices as destination for the  // above picked source  for (j = 0; j < V; j++) {  // If vertex k is on the shortest path  // from i to j, then update the value of  // dist[i][j]  if (dist[i][k] + dist[k][j]  < dist[i][j])  dist[i][j]  = dist[i][k] + dist[k][j];  }  }  }  // Print the shortest distance matrix  printSolution(dist);  }  void printSolution(int dist[][])  {  System.out.println(  'The following matrix shows the shortest '  + 'distances between every pair of vertices');  for (int i = 0; i < V; ++i) {  for (int j = 0; j < V; ++j) {  if (dist[i][j] == INF)  System.out.print('INF ');  else  System.out.print(dist[i][j] + ' ');  }  System.out.println();  }  }  // Driver's code  public static void main(String[] args)  {  /* Let us create the following weighted graph  10  (0)------->(3) | /|5 | |  | | 1 |/ |  (1)------->(2) 3 */ int grafico[][] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, {INF,INF,INF, 0} };  AllPairShortestPath a = new AllPairShortestPath();  // Chiamata di funzione a.floydWarshall(graph);  } } // Contributo di Aakash Hasija>
Python3 
# Python3 Program for Floyd Warshall Algorithm # Number of vertices in the graph V = 4 # Define infinity as the large # enough value. This value will be # used for vertices not connected to each other INF = 99999 # Solves all pair shortest path # via Floyd Warshall Algorithm def floydWarshall(graph):  ''' dist[][] will be the output   matrix that will finally  have the shortest distances   between every pair of vertices '''  ''' initializing the solution matrix   same as input graph matrix  OR we can say that the initial   values of shortest distances  are based on shortest paths considering no   intermediate vertices ''' dist = list(map(lambda i: list(map(lambda j: j, i)), graph))  ''' Add all vertices one by one   to the set of intermediate  vertices.  --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici tali che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.  ----> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} ''' for k in range(V): # seleziona tutti i vertici come sorgente uno per uno for i in range(V): # Scegli tutti i vertici come destinazione per la # sorgente scelta sopra per j in range(V): # Se il vertice k si trova sul percorso più breve da # i a j, aggiorna il valore di dist[i][ j] dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j] ) printSolution(dist) # Una funzione di utilità per stampare la soluzione def printSolution (dist): print('La matrice seguente mostra le distanze più brevi tra ogni coppia di vertici') for i in range(V): for j in range(V): if(dist[i][j] == INF): print('%7s' % ('INF'), end=' ') else: print('%7d	' % (dist[i][j]), end=' ') if j == V-1: print() # Codice del driver if __name__ == '__main__': ''' 10 (0)------ ->(3) | /|5 | |  | | 1 |/ |  (1)------->(2) 3 ''' grafico = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0 , 1], [INF, INF, INF, 0] ] # Chiamata di funzione floydWarshall(graph) # Questo codice è fornito da Mythri J L>
C# 
// C# program for Floyd Warshall All // Pairs Shortest Path algorithm. using System; public class AllPairShortestPath {  readonly static int INF = 99999, V = 4;  void floydWarshall(int[, ] graph)  {  int[, ] dist = new int[V, V];  int i, j, k;  // Initialize the solution matrix  // same as input graph matrix  // Or we can say the initial  // values of shortest distances  // are based on shortest paths  // considering no intermediate  // vertex  for (i = 0; i < V; i++) {  for (j = 0; j < V; j++) {  dist[i, j] = graph[i, j];  }  }  /* Add all vertices one by one to  the set of intermediate vertices.  --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici in modo tale che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.  ---> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} */ for (k = 0; k< V; k++) {  // Pick all vertices as source  // one by one  for (i = 0; i < V; i++) {  // Pick all vertices as destination  // for the above picked source  for (j = 0; j < V; j++) {  // If vertex k is on the shortest  // path from i to j, then update  // the value of dist[i][j]  if (dist[i, k] + dist[k, j]  < dist[i, j]) {  dist[i, j]  = dist[i, k] + dist[k, j];  }  }  }  }  // Print the shortest distance matrix  printSolution(dist);  }  void printSolution(int[, ] dist)  {  Console.WriteLine(  'Following matrix shows the shortest '  + 'distances between every pair of vertices');  for (int i = 0; i < V; ++i) {  for (int j = 0; j < V; ++j) {  if (dist[i, j] == INF) {  Console.Write('INF ');  }  else {  Console.Write(dist[i, j] + ' ');  }  }  Console.WriteLine();  }  }  // Driver's Code  public static void Main(string[] args)  {  /* Let us create the following  weighted graph  10  (0)------->(3) | /|5 | |  | | 1 |/ |  (1)------->(2) 3 */ int[, ] grafico = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0 , 1 }, {INF,INF,INF, 0 } };  AllPairShortestPath a = new AllPairShortestPath();  // Chiamata di funzione a.floydWarshall(graph);  } } // Questo articolo è un contributo di // Abdul Mateen Mohammed>
Javascript 
// A JavaScript program for Floyd Warshall All  // Pairs Shortest Path algorithm.  var INF = 99999;  class AllPairShortestPath {  constructor() {  this.V = 4;  }  floydWarshall(graph) {  var dist = Array.from(Array(this.V), () =>nuovo Array(this.V).fill(0));  var i, j, k;  // Inizializza la matrice della soluzione // come la matrice del grafico di input // Oppure possiamo dire che i valori iniziali // delle distanze più brevi // sono basati sui cammini più brevi // non considerando alcun vertice intermedio // per (i = 0; i< this.V; i++) {  for (j = 0; j < this.V; j++) {  dist[i][j] = graph[i][j];  }  }  /* Add all vertices one by one to  the set of intermediate vertices.  --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici in modo tale che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.  ---> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} */ for (k = 0; k< this.V; k++) {  // Pick all vertices as source  // one by one  for (i = 0; i < this.V; i++) {  // Pick all vertices as destination  // for the above picked source  for (j = 0; j < this.V; j++) {  // If vertex k is on the shortest  // path from i to j, then update  // the value of dist[i][j]  if (dist[i][k] + dist[k][j] < dist[i][j]) {  dist[i][j] = dist[i][k] + dist[k][j];  }  }  }  }  // Print the shortest distance matrix  this.printSolution(dist);  }  printSolution(dist) {  document.write(  'Following matrix shows the shortest ' +  'distances between every pair of vertices '  );  for (var i = 0; i < this.V; ++i) {  for (var j = 0; j < this.V; ++j) {  if (dist[i][j] == INF) {  document.write(' INF ');  } else {  document.write('  ' + dist[i][j] + ' ');  }  }  document.write(' ');  }  }  }  // Driver Code  /* Let us create the following  weighted graph  10  (0)------->(3) | /|5 | |  | | 1 |/ |  (1)------->(2) 3 */ var grafico = [ [0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1] , [INF,INF,INF,0],];  var a = new AllPairShortestPath();  // Stampa la soluzione a.floydWarshall(graph);    // Questo codice è fornito da rdtaank.>
PHP 
 // PHP Program for Floyd Warshall Algorithm  // Solves the all-pairs shortest path problem // using Floyd Warshall algorithm  function floydWarshall ($graph, $V, $INF) { /* dist[][] will be the output matrix   that will finally have the shortest   distances between every pair of vertices */ $dist = array(array(0,0,0,0), array(0,0,0,0), array(0,0,0,0), array(0,0,0,0)); /* Initialize the solution matrix same   as input graph matrix. Or we can say the   initial values of shortest distances are   based on shortest paths considering no   intermediate vertex. */ for ($i = 0; $i < $V; $i++) for ($j = 0; $j < $V; $j++) $dist[$i][$j] = $graph[$i][$j]; /* Add all vertices one by one to the set   of intermediate vertices.   --->Prima dell'inizio di un'iterazione, abbiamo le distanze più brevi tra tutte le coppie di vertici tali che le distanze più brevi considerino solo i vertici nell'insieme {0, 1, 2, .. k-1} come vertici intermedi.   ----> Dopo la fine di un'iterazione, il vertice n. k viene aggiunto all'insieme dei vertici intermedi e l'insieme diventa {0, 1, 2, .. k} */ for ($k = 0; $k< $V; $k++) { // Pick all vertices as source one by one  for ($i = 0; $i < $V; $i++) { // Pick all vertices as destination  // for the above picked source  for ($j = 0; $j < $V; $j++) { // If vertex k is on the shortest path from  // i to j, then update the value of dist[i][j]  if ($dist[$i][$k] + $dist[$k][$j] < $dist[$i][$j]) $dist[$i][$j] = $dist[$i][$k] + $dist[$k][$j]; } } } // Print the shortest distance matrix  printSolution($dist, $V, $INF); } /* A utility function to print solution */ function printSolution($dist, $V, $INF) { echo 'The following matrix shows the ' . 'shortest distances between ' . 'every pair of vertices 
'; for ($i = 0; $i < $V; $i++) { for ($j = 0; $j < $V; $j++) { if ($dist[$i][$j] == $INF) echo 'INF ' ; else echo $dist[$i][$j], ' '; } echo '
'; } } // Drivers' Code // Number of vertices in the graph  $V = 4 ; /* Define Infinite as a large enough  value. This value will be used for vertices not connected to each other */ $INF = 99999 ; /* Let us create the following weighted graph   10  (0)------->(3) | /|5 | |   | | 1 |/ |  (1)------->(2) 3 */ $grafico = array(array(0, 5, $INF, 10), array($INF, 0, 3, $INF), array($ INF, $INF, 0, 1), array($INF, $INF, $INF, 0)); // Chiamata di funzione floydWarshall($graph, $V, $INF); // Questo codice è un contributo di Ryuga ?>>
Produzione 
The following matrix shows the shortest distances between every pair of vertices 0 5 8 9 INF 0 3 4 INF INF 0 1 INF INF INF 0>

Analisi della complessità dell'algoritmo di Floyd Warshall:

  • Complessità temporale: O(V3), dove V è il numero di vertici nel grafico ed eseguiamo tre cicli nidificati ciascuno di dimensione V
  • Spazio ausiliario: O(V2), per creare una matrice 2-D per memorizzare la distanza più breve per ciascuna coppia di nodi.

Nota : Il programma sopra stampa solo le distanze più brevi. Possiamo modificare la soluzione per stampare i percorsi più brevi anche memorizzando le informazioni del predecessore in una matrice 2D separata.

proprietà acide nei DBMS

Perché l'algoritmo di Floyd-Warshall è migliore per i grafici densi e non per i grafici sparsi?

Grafico denso : Un grafico in cui il numero di spigoli è significativamente molto più alto del numero di vertici.
Grafico sparso : Un grafico in cui il numero di spigoli è molto basso.

Non importa quanti spigoli ci sono nel grafico Algoritmo di Floyd Warshall corre per O(V3) orari per cui è più adatto Grafici densi . Nel caso di grafici sparsi, Algoritmo di Johnson è più adatto.

  • Come rilevare il ciclo negativo in un grafico utilizzando l'algoritmo di Floyd Warshall?
  • In cosa differisce l’algoritmo di Floyd-warshall dall’algoritmo di Dijkstra?
  • In che modo l'algoritmo Floyd-warshall è diverso dall'algoritmo Bellman-Ford?

Applicazioni nel mondo reale dell'algoritmo di Floyd-Warshall:

  • Nelle reti di computer, l'algoritmo può essere utilizzato per trovare il percorso più breve tra tutte le coppie di nodi in una rete. Questo è definito come instradamento della rete .
  • Connettività di volo Nel settore dell'aviazione per trovare il percorso più breve tra gli aeroporti.
  • GIS ( Sistemi di informazione geografica ) le applicazioni spesso implicano l'analisi di dati spaziali, come le reti stradali, per trovare i percorsi più brevi tra le località.
  • L'algoritmo di Kleene che è una generalizzazione di floyd warshall, può essere utilizzata per trovare un'espressione regolare per un linguaggio regolare.