El Algorisme de Floyd-Warshall , que porta el nom dels seus creadors Robert Floyd i Stephen Warshall , és un algorisme fonamental en informàtica i teoria de grafs. S'utilitza per trobar els camins més curts entre tots els parells de nodes en un gràfic ponderat. Aquest algorisme és molt eficient i pot gestionar gràfics amb tots dos positiu i n pesos de vora negatius , el que la converteix en una eina versàtil per resoldre una àmplia gamma de problemes de xarxa i connectivitat.
Taula de contingut
- Algoritme de Floyd Warshall
- Idea darrere de l'algoritme de Floyd Warshall
- Algoritme de Floyd Warshall Algoritme
- Pseudocodi de l'algoritme de Floyd Warshall
- Il·lustració de l'algoritme de Floyd Warshall
- Anàlisi de complexitat de l'algoritme de Floyd Warshall
- Per què l'algoritme de Floyd-Warshall és millor per a gràfics densos i no per a gràfics dispersos?
- Preguntes importants d'entrevista relacionades amb Floyd-Warshall
- Aplicacions del món real de l'algoritme de Floyd-Warshall
Algoritme de Floyd Warshall:
El Algoritme de Floyd Warshall és un algorisme del camí més curt de tots els parells a diferència Dijkstra i Bellman Ford que són algorismes de camí més curt d'una sola font. Aquest algorisme funciona tant per a dirigit i ponderat no dirigit gràfics. Però, no funciona per als gràfics amb cicles negatius (on la suma de les arestes en un cicle és negativa). Segueix Programació dinàmica enfocament per comprovar tots els camins possibles que passen per tots els nodes possibles per tal de calcular la distància més curta entre cada parell de nodes.
pandes i numpy
Idea darrere de l'algoritme de Floyd Warshall:
Suposem que tenim un gràfic G[][] amb EN vèrtexs de 1 a N . Ara hem d'avaluar a shortestPathMatrix[][] on s hortestPathMatrix[i][j] representa el camí més curt entre els vèrtexs i i j .
Òbviament el camí més curt entre i a j en tindrà alguna k nombre de nodes intermedis. La idea darrere de l'algoritme de Floyd Warshall és tractar tots i cadascun dels vèrtexs 1 a N com a node intermedi un per un.
La figura següent mostra la propietat òptima de la subestructura anterior a l'algorisme de Floyd Warshall:
Algoritme de Floyd Warshall Algoritme:
- Inicieu la matriu de solució igual que la matriu del gràfic d'entrada com a primer pas.
- A continuació, actualitzeu la matriu de solució considerant tots els vèrtexs com un vèrtex intermedi.
- La idea és escollir tots els vèrtexs un per un i actualitzar tots els camins més curts que inclouen el vèrtex escollit com a vèrtex intermedi en el camí més curt.
- Quan triem el número de vèrtex k com a vèrtex intermedi, ja hem considerat vèrtexs {0, 1, 2, .. k-1} com a vèrtexs intermedis.
- Per cada parella (i, j) dels vèrtexs d'origen i de destinació respectivament, hi ha dos casos possibles.
- k no és un vèrtex intermedi en el camí més curt des de i a j . Mantenim el valor de dist[i][j] com és.
- k és un vèrtex intermedi en el camí més curt des de i a j . Actualitzem el valor de dist[i][j] com dist[i][k] + dist[k][j], si dist[i][j]> dist[i][k] + dist[k][j]
Pseudocodi de l'algoritme de Floyd Warshall:>
Per a k = 0 a n – 1
Per i = 0 a n – 1
Per a j = 0 a n – 1
Distància[i, j] = min(Distància[i, j], Distància[i, k] + Distància[k, j])on i = node font, j = node de destinació, k = node intermedi
Il·lustració de l'algoritme de Floyd Warshall:
Pràctica recomanada Prova-ho!Suposem que tenim un gràfic tal com es mostra a la imatge:
Pas 1 : Inicialitzeu la matriu Distància[][] utilitzant el gràfic d'entrada de manera que Distància[i][j]= pes de la vora des de i a j , també Distància[i][j] = Infinit si no hi ha cap vora des de i a j.
Pas 2 : Tractar el node A com a node intermedi i calculeu la Distància[][] per a cada parell de nodes {i,j} utilitzant la fórmula:
tutorial del llenguatge de programació java= Distància[i][j] = mínima (Distància[i][j], (Distància des de i fins a A ) + (Distància des de A a j))
= Distància[i][j] = mínima (Distància[i][j], Distància[i][ A ] + Distància[ A ][j])Pas 3 : Tractar el node B com a node intermedi i calculeu la Distància[][] per a cada parell de nodes {i,j} utilitzant la fórmula:
= Distància[i][j] = mínima (Distància[i][j], (Distància des de i fins a B ) + (Distància des de B a j))
= Distància[i][j] = mínima (Distància[i][j], Distància[i][ B ] + Distància[ B ][j])Pas 4 : Tractar el node C com a node intermedi i calculeu la Distància[][] per a cada parell de nodes {i,j} utilitzant la fórmula:
= Distància[i][j] = mínima (Distància[i][j], (Distància des de i fins a C ) + (Distància des de C a j))
= Distància[i][j] = mínima (Distància[i][j], Distància[i][ C ] + Distància[ C ][j])Pas 5 : Tractar el node D com a node intermedi i calculeu la Distància[][] per a cada parell de nodes {i,j} utilitzant la fórmula:
pagar amb git= Distància[i][j] = mínima (Distància[i][j], (Distància des de i fins a D ) + (Distància des de D a j))
= Distància[i][j] = mínima (Distància[i][j], Distància[i][ D ] + Distància[ D ][j])Pas 6 : Tractar el node I com a node intermedi i calculeu la Distància[][] per a cada parell de nodes {i,j} utilitzant la fórmula:
què és un ubuntu essencial per a la construcció= Distància[i][j] = mínima (Distància[i][j], (Distància des de i fins a I ) + (Distància des de I a j))
= Distància[i][j] = mínima (Distància[i][j], Distància[i][ I ] + Distància[ I ][j])Pas 7 : Com que tots els nodes s'han tractat com un node intermedi, ara podem tornar la matriu Distància[][] actualitzada com a matriu de resposta.
A continuació es mostra la implementació de l'enfocament anterior:
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. --->Abans de començar una iteració, tenim les distàncies més curtes entre tots els parells de vèrtexs de manera que les distàncies més curtes consideren només els vèrtexs del conjunt {0, 1, 2, .. k-1} com a vèrtexs intermedis. ----> Després del final d'una iteració, el vèrtex núm. k s'afegeix al conjunt de vèrtexs intermedis i el conjunt es converteix en {0, 1, 2, .. k} */ per a (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]; } } } // Imprimeix la matriu de distància més curta printSolution(dist); } /* Una funció d'utilitat per imprimir la solució */ 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 } }; // Crida a la funció floydWarshall(graph); retorn 0; } // Aquest codi és aportat per Mythri J L>>>C(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 } }; // Crida a la funció floydWarshall(graph); retorn 0; }>>> Java(3) | /| 5 | | | | 1 |/ | (1)------->(2) 3 */ int graph[][] = {{ 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0, 1 }, { INF, INF, INF, 0 } }; AllPairShortestPath a = nou AllPairShortestPath(); // Crida a la funció a.floydWarshall(graph); } } // Contribució d'Aakash Hasija>>> Python 3Abans de començar una iteració, tenim les distàncies més curtes entre tots els parells de vèrtexs de manera que les distàncies més curtes consideren només els vèrtexs del conjunt {0, 1, 2, .. k-1} com a vèrtexs intermedis. ----> Després del final d'una iteració, el vèrtex núm. k s'afegeix al conjunt de vèrtexs intermedis i el conjunt es converteix en {0, 1, 2, .. k} ''' per a k dins l'interval (V): # escolliu tots els vèrtexs com a font un per un per a i en rang (V): # Escolliu tots els vèrtexs com a destinació per a la font seleccionada # a dalt per a j a l'interval (V): # Si el vèrtex k es troba al camí més curt de # i a j, actualitzeu el valor de dist[i][ j] dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j] ) printSolution(dist) # Una funció d'utilitat per imprimir la solució def printSolution (dist): print('La matriu següent mostra les distàncies més curtes entre cada parell de vèrtexs') per a i en el rang (V): per a j en el rang (V): if(dist[i][j] == INF): print('%7s'% ('INF'), final='') else: print('%7d '% (dist[i][j]), end=' ') if j == V-1: print() # Codi del controlador if __name__ == '__main__': ''' 10 (0)------ ->(3) | /| 5 | | | | 1 |/ | (1)------->(2) 3 ''' gràfic = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0 , 1], [INF, INF, INF, 0] ] # Crida a la funció floydWarshall(graph) # Aquest codi és aportat per 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. --->Abans de començar una iteració, tenim les distàncies més curtes entre tots els parells de vèrtexs de manera que les distàncies més curtes consideren només els vèrtexs del conjunt {0, 1, 2, .. k-1} com a vèrtexs intermedis. ---> Després del final d'una iteració, el vèrtex núm. k s'afegeix al conjunt de vèrtexs intermedis i el conjunt es converteix en {0, 1, 2, .. k} */ per a (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[, ] gràfic = { { 0, 5, INF, 10 }, { INF, 0, 3, INF }, { INF, INF, 0 , 1 }, { INF, INF, INF, 0 } }; AllPairShortestPath a = nou AllPairShortestPath(); // Crida a la funció a.floydWarshall(graph); } } // Aquest article és contribuït per // Abdul Mateen Mohammed>>>JavascriptAbans de començar una iteració, tenim les distàncies més curtes entre tots els parells de vèrtexs de manera que les distàncies més curtes consideren només els vèrtexs del conjunt {0, 1, 2, .. k-1} com a vèrtexs intermedis. ---> Després del final d'una iteració, el vèrtex núm. k s'afegeix al conjunt de vèrtexs intermedis i el conjunt es converteix en {0, 1, 2, .. k} */ per a (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 gràfic = [ [0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1] , [INF, INF, INF, 0], ]; var a = nou AllPairShortestPath(); // Imprimeix la solució a.floydWarshall(graph); // Aquest codi és aportat per rdtaank.>>> PHP(3) | /| 5 | | | | 1 |/ | (1)------->(2) 3 */ $graph = array(array(0, 5, $INF, 10), array($INF, 0, 3, $INF), array($ INF, $INF, 0, 1), matriu ($INF, $INF, $INF, 0)); // Crida a la funció floydWarshall($graph, $V, $INF); // Aquest codi és aportat per Ryuga ?>> Sortida
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>
Anàlisi de complexitat de l'algoritme de Floyd Warshall:
- Complexitat temporal: O (V3), on V és el nombre de vèrtexs del gràfic i executem tres bucles imbricats cadascun de mida V
- Espai auxiliar: O (V2), per crear una matriu 2-D per tal d'emmagatzemar la distància més curta per a cada parell de nodes.
Nota : El programa anterior només imprimeix les distàncies més curtes. També podem modificar la solució per imprimir els camins més curts emmagatzemant la informació del predecessor en una matriu 2D separada.
Per què l'algoritme de Floyd-Warshall és millor per a gràfics densos i no per a gràfics dispersos?
Gràfic dens : Un gràfic en què el nombre d'arestes és significativament molt superior al nombre de vèrtexs.
Gràfic escàs : Un gràfic en el qual el nombre d'arestes és molt baix.No importa quantes arestes hi hagi al gràfic, el Algoritme de Floyd Warshall corre per O(V3) vegades, per tant, és el més adequat Gràfics densos . En el cas de gràfics dispersos, Algoritme de Johnson és més adequat.
Preguntes importants de l'entrevista relacionades amb Floyd-Warshall:
- Com detectar el cicle negatiu en un gràfic mitjançant l'algoritme de Floyd Warshall?
- En què és diferent l'algoritme de Floyd-warshall de l'algoritme de Dijkstra?
- En què és diferent l'algoritme de Floyd-warshall de l'algoritme de Bellman-Ford?
Aplicacions del món real de l'algoritme de Floyd-Warshall:
- En xarxes d'ordinadors, l'algoritme es pot utilitzar per trobar el camí més curt entre tots els parells de nodes d'una xarxa. Això s'anomena com encaminament de la xarxa .
- Connectivitat de vol A la indústria de l'aviació per trobar el camí més curt entre els aeroports.
- GIS ( Sistemes d'informació geogràfica ) les aplicacions sovint impliquen l'anàlisi de dades espacials, com ara xarxes de carreteres, per trobar els camins més curts entre ubicacions.
- algorisme de Kleene que és una generalització de Floyd Warshall, es pot utilitzar per trobar expressió regular per a un llenguatge regular.