0
503
Views¿Por qué floyd warshall solo usa una matriz de distancia?
Leí el pseudocódigo del algoritmo de floyd warshall 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if Pero solo usa una matriz dist para guardar distancias. Creo que debería haber n matrices de distancia, donde n es el número de vértices, o al menos necesitamos dos matrices de distancia. uno almacena la ruta más corta actual dentro de los vértices k-1, el otro almacena la ruta más corta dentro de los vértices k, luego el primero almacena la ruta más corta dentro de k+1, .... ¿Cómo podemos simplemente almacenar las nuevas distancias de la ruta más corta dentro de los vértices? k en la matriz original para distancias dentro de los vértices k-1?
esta imagen muestra que necesitamos D0, D1, D2....D(n)
2 answers
Answer question0
Tiene razón en el sentido de que la fórmula original requiere que los cálculos para el paso k necesiten usar los cálculos del paso k-1 :
Eso se puede organizar fácilmente si, como usted dice, la primera matriz se usa para almacenar valores del paso k-1 segunda se usa para almacenar valores de k , la primera se usa nuevamente para almacenar valores de k+1 , etc.
Pero, si usamos la misma matriz al actualizar los valores, en la fórmula anterior podríamos usar accidentalmente en vez de
si el valor del índice
i,k ya se actualizó durante la ronda actual k , o podríamos obtener en vez de
si se ha actualizado el valor del índice
k,j . ¿No será eso una violación del algoritmo, ya que estamos usando la fórmula de actualización recursiva incorrecta?
Bueno en realidad no. Recuerde, el algoritmo de Floyd-Warshall se ocupa de la restricción "sin ciclos negativos", lo que significa que no hay ciclo con bordes que sumen un valor negativo. Esto significa que para cualquier k el camino más corto del nodo k al nodo k es 0 (de lo contrario, significaría que hay un camino de k a k con bordes que suman un valor negativo). Así que por definición:
Ahora, tomemos la primera fórmula y reemplacemos j con k :
Y luego reemplacemos en la misma fórmula 'i' con 'k':
Así que básicamente, tendrá el mismo valor que
y
tendrá el mismo valor que
, por lo que realmente no importa si estos valores se actualizan o no durante el ciclo 'k' y, por lo tanto, puede actualizar la misma matriz mientras la lee sin romper el algoritmo.
0
Tienes razón en parte aquí.
La salida del algoritmo Floyd Warshall (es decir, la matriz NxN) NO ayuda a reconstruir el camino más corto real entre dos vértices dados.
Estos caminos se pueden recuperar si retenemos una matriz padre P, tal que almacene el último vértice intermedio utilizado para cada par de vértices (x, y). Digamos que este valor es k.
El camino más corto de x a y es la concatenación del camino más corto de x a k con el camino más corto de k a y, que se puede reconstruir recursivamente dada la matriz P.
Tenga en cuenta, sin embargo, que la mayoría de las aplicaciones de todos los pares solo necesitan la matriz de distancia resultante. Estos trabajos son para lo que se diseñó el algoritmo de Floyd.