Floyd-Warshall kullanarak tüm en kısa yolları ve mesafeleri bulma

Question

İlk önce, biraz arka plan: Temel grafik algoritmaları (Dijkstra, Floyd-Warshall, Bellman-Ford, vb.) Olarak kullanmak için basit bir grafik sınıfı oluşturmaya çalışıyorum. Yaklaşan bir program yarışması için referans sayfası.

Şimdiye kadar Floyd-Warshall bir işleyen sürümüne sahip ancak olumsuz şimdiye kadar sadece en kısa mesafe değerini bana ikisi arasında düğümleri değil kısa yolu gidiyor olmasıdır. Tercihen, yeniden inşa etmek için başka bir işlevi çağırmak yerine, yol yapımının algoritmanın kendisinde yer almasını isterim.

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

İşte 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

örnek grafiği kullanıyorum veriler var: Burada

kullanıyorum veri yapıları ilgili bazı bilgiler verilmiştir

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 

ve burada istenen değer "yol" değişkeninde (Dijkstra'yı düğümlerin her birinden çalıştırarak elde edildi):

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 

Şu anda algoritma için kullandığım kodun bir bağlantısı: (via PasteBin).

Herhangi bir yardım büyük takdir!

Düzenleme

: Ben yol matrisi oluşturmak için Wikipedia's code çalıştı İşte sonuç: Bu tür işler ancak "tek" adımlarını temsil eden söz konusu olduğunda sorunları vardır

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 

. Örneğin, düğüm 0'dan düğüme 1 olan yol her yerde tanımsızdır. (Ama yine de, öneri için Nali4Freedom teşekkürler)

Answer 1

Huzzah!

Ben Wikipedia'nın kod parçacığını ekleyerek sonuçlarına iyi bir sabit bakış vardı ve ayrı bir işlevinin çağrılması gerek kalmadan benim sonuçlarına yapıp sonuçlarını dönüştürmek için bir adaptör ile geldi: Esasen bu

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

A düğümünden B düğümünden alındığında, orijinal grafikte varsa kenar ekleyerek (mid_node == INF) tek adımı telafi eder. Alternatif olarak, işaret ettiği düğüm (this->path[mid_node][end_node] != INF) hedef düğümüne sadece bir basamak taşıyorsa, nereye gittiğini bulana kadar kazar.

Yardımınız için teşekkürler, sanırım yüksek sesle düşünmek için birine ihtiyacım vardı!

Answer 2

Vikipedi bazı iyi bilgi ve pseudocode vardır. Temel olarak sadece bir | V | x | V | 'next' matrisi, i, j elemanının, j düğümünden j düğümüne gitmek için gitmeniz gereken köşe noktasını içerir. I'den j'ye olan en kısa yol, i'den sonraki [i] [j] 'ye ve bir sonraki [i] [j]' ye j olarak yolunu verebilir. Yolun tam yoluna sahip olana kadar bu şekilde yinelenen yolu ayrıştırmaya devam edersiniz.