FLOYD WARSHALL ALGORITHM - TECHCODEVIEW.COM

De Floyd-Warshall algoritm , uppkallad efter dess skapare Robert Floyd och Stephen Warshall , är en grundläggande algoritm inom datavetenskap och grafteori. Den används för att hitta de kortaste vägarna mellan alla nodpar i en viktad graf. Denna algoritm är mycket effektiv och kan hantera grafer med båda positiv och n egativa kantvikter , vilket gör det till ett mångsidigt verktyg för att lösa ett brett utbud av nätverks- och anslutningsproblem.

Innehållsförteckning

Floyd Warshall-algoritm
Idén bakom Floyd Warshall-algoritmen
Floyd Warshall Algoritm Algoritm
Pseudo-koden för Floyd Warshall Algorithm
Illustration av Floyd Warshall-algoritmen
Komplexitetsanalys av Floyd Warshall-algoritmen
Varför Floyd-Warshall Algorithm bättre för täta grafer och inte för glesa grafer?
Viktiga intervjufrågor relaterade till Floyd-Warshall
Verkliga tillämpningar av Floyd-Warshall Algorithm

Floyd-Warshall-Algorithm-banner

Floyd Warshall Algoritm:

De Floyd Warshall-algoritm är en kortaste väg-algoritm för alla par till skillnad från Dijkstra och Bellman Ford som är algoritmer för den kortaste vägen för en enda källa. Denna algoritm fungerar för både riktad och oriktad viktad grafer. Men det fungerar inte för graferna med negativa cykler (där summan av kanterna i en cykel är negativ). Det följer Dynamisk programmering tillvägagångssätt för att kontrollera varje möjlig väg som går via varje möjlig nod för att beräkna det kortaste avståndet mellan varje nodpar.
formatera java-sträng

Idé bakom Floyd Warshall-algoritmen:

Antag att vi har en graf G[][] med I hörn från 1 till N . Nu måste vi utvärdera en shortestPathMatrix[][] vart är hortestPathMatrix[i][j] representerar den kortaste vägen mellan hörn i och j .

Uppenbarligen den kortaste vägen mellan i till j kommer att ha några k antal mellannoder. Tanken bakom floyd warshall-algoritmen är att behandla varje vertex från 1 till N som en mellannod en efter en.

Följande figur visar ovanstående optimala underbyggnadsegenskap i Floyd Warshall-algoritmen:

Floyd Warshall Algoritm Algoritm:

Initiera lösningsmatrisen på samma sätt som inmatningsgrafmatrisen som ett första steg.
Uppdatera sedan lösningsmatrisen genom att betrakta alla hörn som en mellanliggande vertex.
Tanken är att välja alla hörn en efter en och uppdatera alla kortaste banor som inkluderar den plockade vertexen som en mellanliggande vertex i den kortaste banan.
När vi väljer vertexnummer k som ett mellanliggande hörn har vi redan betraktat hörn {0, 1, 2, .. k-1} som mellanliggande hörn.
För varje par (I j) av källan respektive destinationspunkten finns det två möjliga fall.
- k är inte ett mellanliggande hörn på kortaste vägen från i till j . Vi behåller värdet av dist[i][j] som det är.
- k är ett mellanliggande hörn i kortaste vägen från i till j . Vi uppdaterar värdet på dist[i][j] som dist[i][k] + dist[k][j], om dist[i][j]> dist[i][k] + dist[k][j]

Pseudo-kod för Floyd Warshall Algorithm:`>`

För k = 0 till n – 1
För i = 0 till n – 1
För j = 0 till n – 1
Avstånd[i, j] = min(Avstånd[i, j], Avstånd[i, k] + Avstånd[k, j])

där i = källnod, j = destinationsnod, k = mellannod

Illustration av Floyd Warshall Algorithm:

Anta att vi har en graf som visas i bilden:

Steg 1 : Initiera matrisen Avstånd[][] med hjälp av inmatningsgrafen så att Avstånd[i][j]= kantens vikt från i till j , även Avstånd[i][j] = Oändligt om det inte finns någon kant från i till j.

Steg 2 : Behandla nod A som en mellannod och beräkna avståndet[][] för varje {i,j} nodpar med hjälp av formeln:
sql server pivot

= Avstånd[i][j] = minimum (Avstånd[i][j], (Avstånd från i till A ) + (Avstånd från A till j))
= Avstånd[i][j] = minimum (Avstånd[i][j], Avstånd[i][ A ] + Avstånd[ A ][j])

Steg 3 : Behandla nod B som en mellannod och beräkna avståndet[][] för varje {i,j} nodpar med hjälp av formeln:

= Avstånd[i][j] = minimum (Avstånd[i][j], (Avstånd från i till B ) + (Avstånd från B till j))
= Avstånd[i][j] = minimum (Avstånd[i][j], Avstånd[i][ B ] + Avstånd[ B ][j])

Steg 4 : Behandla nod C som en mellannod och beräkna avståndet[][] för varje {i,j} nodpar med hjälp av formeln:

= Avstånd[i][j] = minimum (Avstånd[i][j], (Avstånd från i till C ) + (Avstånd från C till j))
= Avstånd[i][j] = minimum (Avstånd[i][j], Avstånd[i][ C ] + Avstånd[ C ][j])

Steg 5 : Behandla nod D som en mellannod och beräkna avståndet[][] för varje {i,j} nodpar med hjälp av formeln:
full huggorm

= Avstånd[i][j] = minimum (Avstånd[i][j], (Avstånd från i till D ) + (Avstånd från D till j))
= Avstånd[i][j] = minimum (Avstånd[i][j], Avstånd[i][ D ] + Avstånd[ D ][j])

Steg 6 : Behandla nod OCH som en mellannod och beräkna avståndet[][] för varje {i,j} nodpar med hjälp av formeln:
int parseint

= Avstånd[i][j] = minimum (Avstånd[i][j], (Avstånd från i till OCH ) + (Avstånd från OCH till j))
= Avstånd[i][j] = minimum (Avstånd[i][j], Avstånd[i][ OCH ] + Avstånd[ OCH ][j])

Steg 7 : Eftersom alla noder har behandlats som en mellannod kan vi nu returnera den uppdaterade Distance[][]-matrisen som vår svarsmatris.

Rekommenderad övning Prova!

Nedan är implementeringen av ovanstående tillvägagångssätt:

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öre start av en iteration har vi kortaste avstånd mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.  ----> Efter slutet av en iteration, vertex nr. k läggs till mängden mellanliggande hörn och mängden blir {0, 1, 2, .. k} */ för (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]>(avstånd[i][k] + dist[k][j]) && (avstånd[k][j] != INF && dist[i][k] != INF)) dist[i][j] = dist[i][k] + dist[k][j];  } } } // Skriv ut den kortaste avståndsmatrisen printSolution(dist); } /* En verktygsfunktion för att skriva 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 } };  // Funktionsanrop floydWarshall(graf);  returnera 0; } // Denna kod är bidragit 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öre start av en iteration har vi kortaste avstånd mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.  ----> Efter slutet av en iteration, vertex nr. k läggs till mängden mellanliggande hörn och mängden blir {0, 1, 2, .. k} */ för (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 } };  // Funktionsanrop floydWarshall(graf);  returnera 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öre start av en iteration har vi kortaste avstånd mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.  ----> Efter slutet av en iteration, vertex nr. k läggs till mängden mellanliggande hörn och mängden blir {0, 1, 2, .. k} */ för (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();  // Funktionsanrop a.floydWarshall(graf);  } } // Bidragit 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.  --->Innan start av en iteration har vi de kortaste avstånden mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.  ----> Efter slutet av en iteration, vertex nr. k läggs till uppsättningen av mellanliggande hörn och mängden blir {0, 1, 2, .. k} ''' för k i intervall (V): # välj alla hörn som källa en efter en för i in range(V): # Välj alla hörn som destination för # ovan valda källa för j i intervall(V): # Om vertex k är på den kortaste vägen från # i till j, uppdatera sedan värdet för dist[i][ j] dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j] ) printSolution(dist) # En verktygsfunktion för att skriva ut lösningen def printSolution (avstånd): print('Följande matris visar de kortaste avstånden mellan varje par av hörn') för i i intervallet(V): för j i intervallet(V): if(avstånd[i][j] == INF): print('%7s' % ('INF'), end=' ') else: print('%7d	' % (avstånd[i][j]), end=' ') if j == V-1: print() # Drivers code 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] ] # Funktionsanrop floydWarshall(graph) # Denna kod har bidragit 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öre start av en iteration har vi kortaste avstånd mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.  ---> Efter slutet av en iteration, vertex nr. k läggs till mängden mellanliggande hörn och mängden blir {0, 1, 2, .. k} */ för (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();  // Funktionsanrop a.floydWarshall(graf);  } } // Den här artikeln är bidragit 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;  // Initiera lösningsmatrisen // samma som inmatad grafmatris // Eller så kan vi säga att de initiala //-värdena för kortaste avstånd // är baserade på kortaste vägar // med tanke på ingen mellanliggande // vertex för (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öre start av en iteration har vi kortaste avstånd mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.  ---> Efter slutet av en iteration, vertex nr. k läggs till mängden mellanliggande hörn och mängden blir {0, 1, 2, .. k} */ för (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);    // Denna kod är bidragit 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öre start av en iteration har vi kortaste avstånd mellan alla par av hörn så att de kortaste avstånden endast betraktar hörnen i mängden {0, 1, 2, .. k-1} som mellanliggande hörn.   ----> Efter slutet av en iteration, vertex nr. k läggs till mängden mellanliggande hörn och mängden blir {0, 1, 2, .. k} */ för ($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)); // Funktionsanrop floydWarshall($graf, $V, $INF); // Denna kod är bidragit av Ryuga ?>>

Produktion

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>

Komplexitetsanalys av Floyd Warshall-algoritmen:

Tidskomplexitet: O(V³), där V är antalet hörn i grafen och vi kör tre kapslade slingor var och en av storlek V
Hjälputrymme: O(V²), för att skapa en 2D-matris för att lagra det kortaste avståndet för varje nodpar.

Notera : Ovanstående program skriver bara ut de kortaste avstånden. Vi kan modifiera lösningen för att skriva ut de kortaste vägarna också genom att lagra föregångarens information i en separat 2D-matris.

Varför Floyd-Warshall Algorithm bättre för täta grafer och inte för glesa grafer?

Tät graf : En graf där antalet kanter är betydligt högre än antalet hörn.
Gles graf : En graf där antalet kanter är mycket lågt.

Oavsett hur många kanter som finns i grafen Floyd Warshall-algoritm körs för O(V³) gånger därför passar den bäst för Täta grafer . När det gäller glesa grafer, Johnsons algoritm är mer lämplig.

Hur upptäcker man negativ cykel i en graf med Floyd Warshall-algoritmen?
Hur skiljer sig Floyd-warshall-algoritmen från Dijkstras algoritm?
Hur skiljer sig Floyd-warshall-algoritmen från Bellman-Ford-algoritmen?

Verkliga tillämpningar av Floyd-Warshall Algorithm:

I datornätverk kan algoritmen användas för att hitta den kortaste vägen mellan alla nodpar i ett nätverk. Detta kallas som nätverksdirigering .
Flight Connectivity I flygbranschen för att hitta den kortaste vägen mellan flygplatserna.
GIS ( Geografiska informationssystem ) applikationer involverar ofta att analysera rumslig data, såsom vägnät, för att hitta de kortaste vägarna mellan platser.
Kleenes algoritm som är en generalisering av floyd warshall, kan användas för att hitta reguljära uttryck för ett vanligt språk.