Algoritme de Floyd-Warshall

Diagrama mostrant les equacions de l'Algoritme de Floyd-Warshall per a calcular els camins més curts entre tots els parells de vèrtiços en un grafo ponderat.

En informàtica, el algoritme de Floyd-Warshall, descrit en 1959 per Bernard Roy, és un algoritme d'anàlisis sobre grafos per a trobar el camí mínim en grafos dirigits ponderats. L'algoritme troba el camí entre tots els parells de vèrtiços en una única eixecució. L'algoritme de Floyd-Warshall és un eixemple de programació dinàmica.

L'algoritme de Warshall

L'algoritme de Warshall és un eixemple d'algoritme booleano. A partir d'una taula inicial composta de 0's (no hi ha correspondència inicial en el grafo) i 1's (hi ha una correspondència, cridara “flecha”, entre nodos), obté una nova matriu denominada “Matriu de Clausura Transitiva” en la que es mostren totes les possibles unions entre nodos, directa o indirectament. És dir, si de “A” a “B” no hi ha una “flecha”, és possible que si haja de “A” a “C” i després de “C” a “B”. Després, este resultat es vorà bolcat en la matriu final.

L'algoritme de Floyd

L'algoritme de Floyd és molt similar, pero treballa en grafos ponderats. És dir, el valor de la “flecha” que representem en la matriu pot ser qualsevol número real o infinit. Infinit marca que no existix unió entre els nodos. Esta volta, el resultat serà una matriu a on estaran representades les distàncies mínimes entre nodos, seleccionant els camins més convenients segons la seua ponderació (“pes”). Per eixemple, si de “A” a “B” hi ha 36 (km), pero de “A” a “C” hi ha 2(km) i de “C” a “B” hi ha 10 (km), l'algoritme nos tornarà finalment que de “A” a “B” hi ha 12 (km).

Els passos a donar en l'aplicació de l'algoritme de Floyd són els següents:

* Formar les matrius inicials C i D, a on C és la matriu de adyacencia, i D és una matriu del mateix tamany carregada en valors inicials Dij = i.

* Es pren k=1.

* Se selecciona la fila i la columna k de la matriu C i llavors, per a i i j, en i≠k, j≠k i i≠j, fem:

Si (Cik + Ckj) < Cij → Dij = Dkj i Cij = Cik + Ckj

En cas contrari, deixem les matrius com estan.

* Si k ≤ n, aumentem k en una unitat i repetim el pas anterior, en cas contrari parem les iteraciones.

* La matriu final C conté els costs òptims per a ser d'un vèrtiç a un atre, mentres que la matriu D conté els penúltims vèrtiços dels camins òptims que unixen dos vèrtiços, lo que permet reconstruir qualsevol camí òptim per a ser d'un vèrtiç a un atre.

Referències

• Cormen (1990). Introduction to Algorithms, 1º Edició edició, MIT Press i McGraw-Hill.
  • Secció 26.2, "The Floyd–Warshall algorithm", pág. 558–565;
  • Secció 26.4, "A general framework for solving path problems in directed graphs", pág. 570–576.
• «Algorithm 97: Shortest Path».5(6)

345.

• Kleene, S. C. (1956). «Representation of events in nerve nets and finite automata», C. E. Shannon i John McCarthy (ed.). Automata Studies, Princeton University Press, pp. 3–42.
• «A theorem on Boolean matrius».9(1)

11–12.

• Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5ª Edició, Addison Wesley.

Vore també

• Algoritme de Dijkstra
• Robert Floyd
• Llistade publicacions de Robert W. Floyd
• Archivat el 27 de abril de 2008 archivat en Wayback Machine.