El algoritmo Floyd-Warshall es la formulación de programación dinámica para resolver el problema de los caminos más cortos de todos los pares. La fórmula recursiva viene dada por:
donde shortestPath (i, j, k) representa la ruta más corta posible de i a j usando vértices solo del conjunto {1,2, …, k} como puntos intermedios en el camino.
- Cómo demostrar que el problema del vendedor de viajes es NP-hard
- Cómo determinar si un DAG tiene una ruta con una longitud mayor que k
- ¿Cuál es la diferencia entre los algoritmos FPgrowth y Apriori en términos de resultados?
- ¿Hay alguna estructura de datos que pueda realizar las funciones de inserción, búsqueda y eliminación en O (log n)?
- ¿Es el algoritmo de búsqueda de Google realmente el mejor?
En base a esta recurrencia, el procedimiento ascendente calcula el valor de shortestPath (i, j, k) en orden de valor creciente de k. Eso significa que podemos encontrar la ruta más corta de i a j con vértices intermedios {1,2, .. k}, si sabemos
- shortestPath (i, j, k-1): la ruta más corta de i a j con vértices intermedios {1, 2, .. k-1}
- shortestPath (i, k, k-1): la ruta más corta de i a k con vértices intermedios {1, 2, .. k-1}
- shortestPath (k, j, k-1): la ruta más corta de k a j con vértices intermedios {1, 2, .. k-1}
Cualquier alteración en los bucles anidados dará resultados incorrectos. Por ejemplo:
para (int i = 0; i <n; i ++) {
para (int j = 0; j <n; j ++) {
para (int k = 0; k <n; k ++) {
if (dis [i] [k] + dis [k] [j] <dis [i] [j])
dis [i] [j] = dis [i] [k] + dis [k] [j];
}
}
}
Tiene un significado completamente diferente. Dará la ruta más corta de i a j con solo un vértice intermedio.
Referencias
- Introducción a los algoritmos, libro de Charles E. Leiserson, Clifford Stein, Ronald Rivest y Thomas H. Cormen.
- Algoritmo de Floyd-Warshall
