Algoritmo de Floyd-Warshall
De Wikipedia, la enciclopedia libre
Este algoritmo intenta resolver el problema de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es similar a construir una tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando la ruta a seguir para ir de la primera ciudad a la segunda.
Esto puede verse de la siguiente manera:
- Sea G=(V,A) un digrafo en el cual cada arco tiene asociado un costo no negativo. El problema es hallar para cualquier par de vértices
(v,w) el camino más corto de v a w.
- G=(V,A), V={1,...,n} y C[i,j] es el costo del arco que va de i a j.
- El algoritmo calcula la serie de matrices
![\begin{matrix} A_0[i,j] = \begin{cases} 0 & \mbox{si }i = j \\ C[i,j] & \mbox{si } i \ne j \end{cases} \\ A_k[i,j] = min(A_{k-1}[i,j],A_{k-1}[i,k]+A_{k-1}[k,j])\end{matrix}](../../../math/9/4/2/9423c5a46f10caa1d73daaa898e7b0cc.png)
- Ak[i,j] significa el costo del camino más corto que va de i a j y que no pasa por algún vértice mayor que k.
- El objetivo es calcular An[i,j]
La programación de este algoritmo puede realizarse simplemente con tres ciclos anidados, de la siguiente manera:
Para k = '0' hasta n hacer
{
Para i = '0' hasta n hacer
{
Para j = '0' hasta n hacer
{
A[i,j] = mínimo(A[i,j],A[i,k] + A[k,j])
}
}
}
