Encontrar todos los caminos y distancias más cortos usando Floyd-Warshall

Question

Primero, un poco de historia: estoy trabajando en construir una clase de gráfico simple con algoritmos de gráficos básicos (Dijkstra, Floyd-Warshall, Bellman-Ford, etc.) para usar como hoja de referencia para una próxima competencia de programación.

Hasta ahora tengo una versión funcional de Floyd-Warshall, pero el inconveniente es que hasta el momento sólo me está poniendo el valor más corto distancia entre dos nodos, no es el camino más corto . Preferiblemente, me gustaría que la creación de ruta se realice dentro del algoritmo en lugar de tener que llamar a otra función para reconstruirla.

Aquí hay algo de información sobre las estructuras de datos que estoy usando:

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

Aquí está el ejemplo datos de gráfico que estoy usando:

INF 10 INF INF INF INF 
INF INF 90 15 INF INF 
INF INF INF INF INF 20 
INF INF INF INF 20 INF 
INF INF 5 INF INF INF 
INF INF INF INF INF INF 

y aquí está la valores deseados para estar en la variable "ruta" (obtenida al ejecutar Dijkstra desde cada uno de los nodos):

INF 0 4 1 3 2 
INF INF 4 1 3 2 
INF INF INF INF INF 2 
INF INF 4 INF 3 2 
INF INF 4 INF INF 2 
INF INF INF INF INF INF 

Aquí hay un enlace al código que estoy usando actualmente para el algoritmo: (via PasteBin).

¡Cualquier ayuda sería muy apreciada!

Editar: me trataron Wikipedia's code para generar la matriz de ruta y aquí está el resultado:

INF INF 4 1 3 4 
INF INF 4 INF 3 4 
INF INF INF INF INF INF 
INF INF 4 INF INF 4 
INF INF INF INF INF 2 
INF INF INF INF INF INF 

Es algo que funciona, pero tiene problemas cuando se trata de representar pasos "individuales". Por ejemplo, la ruta desde el nodo 0 al nodo 1 no está definida en todas partes. (Pero no obstante, gracias Nali4Freedom por la sugerencia)

Answer 1

¡Hurra!

tuve una buena mirada dura en los resultados de la adición de fragmento de código de Wikipedia y se me ocurrió con un adaptador para convertir es resultados en mis resultados sin la necesidad de llamar a una función separada:

// Time to clean up the path graph... 
for (int st_node = 0; st_node < this->size; st_node++) 
{ 
    for (int end_node = 0; end_node < this->size; end_node++) 
    { 
     int mid_node = this->path[st_node][end_node]; 

     if (mid_node == INF) 
     { 
      // There is no mid_node, it's probably just a single step. 
      if (this->graph[st_node][end_node] != INF) 
      { 
       this->path[st_node][end_node] = st_node; 
      } 

     } else { 
      // The mid_node may be part of a multi-step, find where it leads. 
      while (this->path[mid_node][end_node] != INF) 
      { 
       if (this->path[mid_node][end_node] == mid_node) { break; } // Infinite loop 
       if (this->path[mid_node][end_node] == INF) { break; } // Dead end 

       mid_node = this->path[mid_node][end_node]; 
      } 

      this->path[st_node][end_node] = mid_node; 

     } // IF mid_node 
    } // FOR end_node 
} // FOR st_node 

Esencialmente esto compensa cuando al pasar del nodo A al nodo B hay un solo paso (mid_node == INF) al agregar el borde si existía en el gráfico original. Alternativamente, si el nodo al que apunta es solo un trampolín hacia el nodo de destino (this->path[mid_node][end_node] != INF), entonces excava hasta que encuentre a dónde conduce.

Gracias por la ayuda chicos, supongo que necesitaba alguien para pensar en voz alta.

Answer 2

Wikipedia tiene una buena información y pseudocode. Básicamente, solo llenas un | V | x | V | La matriz 'siguiente' donde el elemento i, j contiene el índice del vértice al que debe ir para pasar del nodo i al nodo j. El camino más corto desde i hasta j se puede dar como la ruta de i a la próxima [i] [j] y de la siguiente [i] [j] a j. Continúa descomponiendo el camino recursivamente de esta manera hasta que tenga la ruta completa.