FLOYD WARSHALL ALGORITHM - TECHCODEVIEW.COM

De Floyd-Warshall algoritme , oppkalt etter skaperne Robert Floyd og Stephen Warshall , er en grunnleggende algoritme innen informatikk og grafteori. Den brukes til å finne de korteste banene mellom alle nodepar i en vektet graf. Denne algoritmen er svært effektiv og kan håndtere grafer med begge positivt og n egative kantvekter , noe som gjør det til et allsidig verktøy for å løse et bredt spekter av nettverks- og tilkoblingsproblemer.

Innholdsfortegnelse

Floyd Warshall-algoritme
Ideen bak Floyd Warshall-algoritmen
Floyd Warshall Algoritme Algoritme
Pseudo-kode for Floyd Warshall Algorithm
Illustrasjon av Floyd Warshall Algorithm
Kompleksitetsanalyse av Floyd Warshall-algoritmen
Hvorfor Floyd-Warshall Algorithm er bedre for tette grafer og ikke for sparsomme grafer?
Viktige intervjuspørsmål knyttet til Floyd-Warshall
Virkelige applikasjoner av Floyd-Warshall Algorithm

Floyd-Warshall-Algorithm-banner

Floyd Warshall-algoritme:

De Floyd Warshall-algoritme er en alle par korteste vei-algoritme i motsetning til Dijkstra og Bellman Ford som er en kildes korteste vei-algoritmer. Denne algoritmen fungerer for både regissert og urettet vektet grafer. Men det fungerer ikke for grafene med negative sykluser (der summen av kantene i en syklus er negativ). Det følger Dynamisk programmering tilnærming for å sjekke alle mulige veier som går via alle mulige noder for å beregne korteste avstand mellom hvert nodepar.
mikrotjenester veiledning

Ideen bak Floyd Warshall-algoritmen:

Anta at vi har en graf G[][] med I hjørner fra 1 til N . Nå må vi vurdere en shortestPathMatrix[][] hvor er hortestPathMatrix[i][j] representerer den korteste veien mellom toppunktene Jeg og j .

Tydeligvis den korteste veien mellom Jeg til j vil ha noen k antall mellomnoder. Ideen bak floyd warshall-algoritmen er å behandle hvert eneste toppunkt fra 1 til N som en mellomnode én etter én.

Følgende figur viser den optimale understrukturegenskapen ovenfor i Floyd Warshall-algoritmen:

Floyd Warshall Algoritme Algoritme:

Initialiser løsningsmatrisen på samme måte som inndatagrafmatrisen som et første trinn.
Oppdater deretter løsningsmatrisen ved å betrakte alle toppunkter som et mellomliggende toppunkt.
Ideen er å velge alle toppunktene en etter en og oppdatere alle korteste veier som inkluderer det valgte toppunktet som et mellomliggende toppunkt i den korteste banen.
Når vi velger toppunktnummer k som et mellomliggende toppunkt har vi allerede vurdert toppunkter {0, 1, 2, .. k-1} som mellomliggende hjørner.
For hvert par (i, j) av henholdsvis kilde- og destinasjonspunktene er det to mulige tilfeller.
- k er ikke et mellomliggende toppunkt i korteste vei fra Jeg til j . Vi beholder verdien av dist[i][j] som det er.
- k er et mellomliggende toppunkt i korteste vei fra Jeg til j . Vi oppdaterer verdien av dist[i][j] som dist[i][k] + dist[k][j], hvis dist[i][j]> dist[i][k] + dist[k][j]

Pseudo-kode for Floyd Warshall Algorithm:`>`

For k = 0 til n – 1
For i = 0 til n – 1
For j = 0 til n – 1
Avstand[i, j] = min(Avstand[i, j], Avstand[i, k] + Avstand[k, j])

hvor i = kildenoden, j = destinasjonsnoden, k = mellomnoden

Illustrasjon av Floyd Warshall Algorithm:

Anta at vi har en graf som vist på bildet:

Trinn 1 : Initialiser Avstand[][]-matrisen ved å bruke inndatagrafen slik at Avstand[i][j]= vekt av kant fra Jeg til j , også Avstand[i][j] = Uendelig hvis det ikke er noen kant fra Jeg til j.

Steg 2 : Behandle node EN som en mellomnode og beregn avstanden[][] for hvert {i,j} nodepar ved å bruke formelen:
3d i autocad

= Avstand[i][j] = minimum (Avstand[i][j], (Avstand fra i til EN ) + (Avstand fra EN til j))
= Avstand[i][j] = minimum (avstand[i][j], avstand[i][ EN ] + Avstand[ EN ][j])

Trinn 3 : Behandle node B som en mellomnode og beregn avstanden[][] for hvert {i,j} nodepar ved å bruke formelen:

= Avstand[i][j] = minimum (Avstand[i][j], (Avstand fra i til B ) + (Avstand fra B til j))
= Avstand[i][j] = minimum (avstand[i][j], avstand[i][ B ] + Avstand[ B ][j])

Trinn 4 : Behandle node C som en mellomnode og beregn avstanden[][] for hvert {i,j} nodepar ved å bruke formelen:

= Avstand[i][j] = minimum (Avstand[i][j], (Avstand fra i til C ) + (Avstand fra C til j))
= Avstand[i][j] = minimum (avstand[i][j], avstand[i][ C ] + Avstand[ C ][j])

Trinn 5 : Behandle node D som en mellomnode og beregn avstanden[][] for hvert {i,j} nodepar ved å bruke formelen:
konvertering fra dato til streng

= Avstand[i][j] = minimum (Avstand[i][j], (Avstand fra i til D ) + (Avstand fra D til j))
= Avstand[i][j] = minimum (avstand[i][j], avstand[i][ D ] + Avstand[ D ][j])

Trinn 6 : Behandle node OG som en mellomnode og beregn avstanden[][] for hvert {i,j} nodepar ved å bruke formelen:
er lik streng i java

= Avstand[i][j] = minimum (Avstand[i][j], (Avstand fra i til OG ) + (Avstand fra OG til j))
= Avstand[i][j] = minimum (avstand[i][j], avstand[i][ OG ] + Avstand[ OG ][j])

Trinn 7 : Siden alle nodene har blitt behandlet som en mellomnode, kan vi nå returnere den oppdaterte Distance[][]-matrisen som vår svarmatrise.

Anbefalt praksis Prøv det!

Nedenfor er implementeringen av tilnærmingen ovenfor:

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.  --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i sett {0, 1, 2, .. k-1} som mellomliggende toppunkter.  ----> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {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]>(avstand[i][k] + dist[k][j]) && (avstand[k][j] != INF && dist[i][k] != INF)) dist[i][j] = dist[i][k] + dist[k][j];  } } } // Skriv ut den korteste avstanden matrisen printSolution(dist); } /* En verktøyfunksjon for å skrive ut løsning */ 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 graf[V][V] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } };  // Funksjonskall floydWarshall(graf);  returner 0; } // Denne koden er bidratt av Mythri J L>

 // 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.  --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i sett {0, 1, 2, .. k-1} som mellomliggende toppunkter.  ----> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {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 graf[V][V] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } };  // Funksjonskall floydWarshall(graf);  returner 0; }>

Java

 // 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.  --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i sett {0, 1, 2, .. k-1} som mellomliggende toppunkter.  ----> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {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 graf[][] = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } };  AllPairShortestPath a = new AllPairShortestPath();  // Funksjonskall a.floydWarshall(graf);  } } // Bidraget av 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.  --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i settet {0, 1, 2, .. k-1} som mellomliggende toppunkter.  ----> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {0, 1, 2, .. k} ''' for k i området(V): # velg alle toppunktene som kilde én etter én for i in område(V): # Velg alle toppunkter som destinasjon for # ovenfor valgte kilde for j i område(V): # Hvis toppunktet k er på den korteste veien fra # i til j, oppdater deretter verdien av dist[i][ j] dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j] ) printSolution(dist) # En verktøyfunksjon for å skrive ut løsningen def printSolution (avstand): print('Følgende matrise viser de korteste avstandene mellom hvert par av hjørner') for i i området(V): for j i området(V): if(avstand[i][j] == INF): print('%7s' % ('INF'), end=' ') else: print('%7d	' % (dist[i][j]), end=' ') if j == V-1: print() # Driverkode if __name__ == '__main__': ''' 10 (0)------ ->(3) | /| 5 | |  | | 1 |/ |  (1)------->(2) 3 ''' graf = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0 , 1], [INF, INF, INF, 0] ] # Funksjonsanrop floydWarshall(graph) # Denne koden er bidratt med Mythri J L>

 // 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.  --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i sett {0, 1, 2, .. k-1} som mellomliggende toppunkter.  ---> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {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[, ] graf = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0 , 1 }, { INF, INF, INF, 0 } };  AllPairShortestPath a = new AllPairShortestPath();  // Funksjonskall a.floydWarshall(graf);  } } // Denne artikkelen er bidratt av // 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), () =>new Array(this.V).fill(0));  var i, j, k;  // Initialiser løsningsmatrisen // samme som inndatagrafmatrisen // Eller vi kan si at de innledende //-verdiene for korteste avstander // er basert på korteste baner // med tanke på ingen mellomliggende // toppunkt for (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.  --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i sett {0, 1, 2, .. k-1} som mellomliggende toppunkter.  ---> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {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 graf = [ [0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1] , [INF, INF, INF, 0], ];  var a = new AllPairShortestPath();  // Skriv ut løsningen a.floydWarshall(graf);    // Denne koden er bidratt av 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.   --->Før start av en iterasjon har vi korteste avstander mellom alle par av toppunkter, slik at de korteste avstandene vurderer bare toppunktene i sett {0, 1, 2, .. k-1} som mellomliggende toppunkter.   ----> Etter slutten av en iterasjon, verteks nr. k legges til settet med mellomliggende toppunkter og settet blir {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 */ $graf = array(array(0, 5, $INF, 10), array($INF, 0, 3, $INF), array($ INF, $INF, 0, 1), array($INF, $INF, $INF, 0)); // Funksjonskall floydWarshall($graf, $V, $INF); // Denne koden er bidratt av Ryuga ?>>

Produksjon

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>

Kompleksitetsanalyse av Floyd Warshall-algoritmen:

Tidskompleksitet: O(V³), der V er antall toppunkter i grafen og vi kjører tre nestede løkker hver av størrelse V
Hjelpeplass: O(V²), for å lage en 2D-matrise for å lagre den korteste avstanden for hvert nodepar.

Merk : Programmet ovenfor skriver kun ut de korteste avstandene. Vi kan modifisere løsningen for å skrive ut de korteste banene også ved å lagre forgjengerinformasjonen i en egen 2D-matrise.

Hvorfor Floyd-Warshall Algorithm er bedre for tette grafer og ikke for sparsomme grafer?

Tett graf : En graf der antall kanter er betydelig mye høyere enn antall toppunkter.
Sparsom graf : En graf der antallet kanter er veldig lavt.

Uansett hvor mange kanter det er i grafen Floyd Warshall-algoritme kjører for O(V³) ganger derfor er det best egnet for Tette grafer . Når det gjelder sparsomme grafer, Johnsons algoritme er mer egnet.

Hvordan oppdage negativ syklus i en graf ved hjelp av Floyd Warshall-algoritmen?
Hvordan er Floyd-warshall-algoritmen forskjellig fra Dijkstras algoritme?
Hvordan er Floyd-warshall-algoritmen forskjellig fra Bellman-Ford-algoritmen?

Virkelige applikasjoner av Floyd-Warshall-algoritmen:

I datanettverk kan algoritmen brukes til å finne den korteste veien mellom alle nodepar i et nettverk. Dette betegnes som nettverksruting .
Flight Connectivity I luftfartsindustrien for å finne den korteste veien mellom flyplassene.
GIS ( Geografiske informasjonssystemer )-applikasjoner innebærer ofte å analysere romlige data, for eksempel veinett, for å finne de korteste veiene mellom lokasjoner.
Kleenes algoritme som er en generalisering av floyd warshall, kan brukes til å finne regulære uttrykk for et vanlig språk.