Floyd-Warshall algoritmo de lógica - Stuck

Question

Estoy tratando de utilizar esta lógica para entender lo que está pasando con el adjacency matrix pero estoy confundida massivley donde dice acerca de espacio intermedio ABCD .....

podría alguien explicar lo que está pasando aquí?

Gracias (etiquetados como Java como el lenguaje de esto fue demostrado a nosotros en, así que si alguien ha publicado ningún ejemplo de código que podían ver que era en ese idioma)

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

Aquí es el código:

for (k = 0; k < n; ++k) { 
    for (i = 0; i < n; ++i) 
     for (j = 0; j < n; ++j) 
      /* If i and j are different nodes and if 
       the paths between i and k and between 
       k and j exist, do */ 
      if ((dist[i][k] * dist[k][j] != 0) && (i != j)) 
       /* See if you can't get a shorter path 
        between i and j by interspacing 
        k somewhere along the current 
        path */ 
       if ((dist[i][k] + dist[k][j] < dist[i][j]) || 
         (dist[i][j] == 0)) 
        dist[i][j] = dist[i][k] + dist[k][j]; 

Answer 1

el algoritmo de Floyd-Warshall hace lo siguiente:

se ve en e ach node (k) y luego busca en cada k -iteración para cada i, j, si podría tener una ruta más corta yendo primero de i a k y luego de k a j.

por lo que parece:

"Mi ruta actualmente corta i-j es de longitud L0, mi momento del camino más corto i-k es de longitud L1, mi momento del camino más corto k-j es de longitud L2.

¿Qué pasa si combino los caminos más cortos Actualmente i to k y k to j a un nuevo camino? ¿Es este nuevo camino más corto que i to k to j mi camino más corto actualmente i to j? Si es así, se acumula y las longitudes L1L2 para calcular la longitud de la nueva ruta más corta."

Eso significa, k es un posible punto de parada para un camino de i a j.

Answer 2

Floyd- Warshall es un problema dynamic programming

es casi estándar (y más fácil) para escribirlo en la versión de 2 dimensiones:.

for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]) 

pero tal vez le ayuda a imaginarlo con la versión de 3 dimensiones, para que pueda ver todos los estados más explícitamente:

for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      dist[k][i][j] = min(dist[k-1][i][k] + dist[k-1][k][j], dist[k-1][i][j]) 

una explicación un poco más profundo de los estados se encuentra en Algorithmist.