Znajdowanie wszystkich najkrótszych ścieżek i odległości za pomocą Floyd-Warshall

Question

Po pierwsze, małe tło: Pracuję nad zbudowaniem prostej klasy grafów z podstawowymi algorytmami graficznymi (Dijkstra, Floyd-Warshall, Bellman-Ford, itp.) Do wykorzystania jako arkusz informacyjny na nadchodzący konkurs programistyczny.

tej pory mam funkcjonującej wersji Floyd-Warshall, ale minusem jest to, że do tej pory to tylko się mi najkrótszą wartość odległości między dwoma węzłami, a nie najkrótszą ścieżkę. Najlepiej chciałbym, aby budowanie ścieżek odbywało się w samym algorytmie, zamiast wywoływania innej funkcji do rekonstrukcji.

Oto kilka informacji na temat struktur danych Używam:

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

Oto dane przykład wykres Używam:

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 

i tu jest żądane wartości znajdują się w zmiennej "ścieżka" (pobierane przez uruchomienie Dijkstra z każdego z węzłów):

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 

Oto link do kodu, którego obecnie używam dla algorytmu: (via PasteBin).

Każda pomoc będzie bardzo ceniona!

Edit: Próbowałem Wikipedia's code wygenerować macierz ścieżkę i oto wynik:

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 

To trochę działa, ale ma problemy, jeśli chodzi o reprezentowanie "single" kroki. Na przykład ścieżka od węzła 0 do węzła 1 jest wszędzie niezdefiniowana. (Niemniej jednak, dziękuję Nali4Freedom za sugestię)

Answer 1

Huzzah!

miałem dobrą twarde spojrzenie na wyniki dodawania fragment kodu Wikipedii i wpadłem z adapterem, aby przekształcić go za wyniki w moich wyników bez konieczności wywoływania odrębną funkcję:

// 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 

Zasadniczo to kompensuje, gdy przechodzenie z węzła A do węzła B jest pojedynczym krokiem (mid_node == INF) przez dodanie krawędzi, jeśli istniała na oryginalnym wykresie. Alternatywnie, jeśli wskazany węzeł jest tylko krokiem do węzła docelowego (this->path[mid_node][end_node] != INF), wówczas wykopuje, aż znajdzie miejsce, do którego prowadzi.

Dzięki za pomoc dla facetów, zgaduję, że po prostu potrzebowałem kogoś, kto by na to głośno!

Answer 2

Wikipedia ma dobre informacje i pseudocode. Zasadniczo po prostu wypełniasz | V | x | V | następna macierz, w której element i, j zawiera indeks wierzchołka, do którego należy przejść, aby uzyskać węzeł i do węzła j. Najkrótsza ścieżka od i do j może być podana jako ścieżka od i do następnej [i] [j] i od następnej [i] [j] do j. Nadal rozkładaj ścieżkę tak rekursywnie, dopóki nie uzyskasz pełnej ścieżki.