Floyd的最短路徑算法C++

我已經在C++中實現了用於加權有向圖的Floyd算法的一個函數，除了當我生成一個路徑矩陣在嘗試到達目的地時給出下一個節點時，它立即將頂點在目標之前而不是矩陣中源的下一個節點。距離矩陣（dist）正確顯示，如果源和目標之間至多有一個節點，那麼整個路徑矩陣是正確的。所以如果從頂點i到j有很長的最短路徑，那麼路徑[i] [j]應該等於一個與我相連的k值，但是它的k值與j相連，我不知道爲什麼。該功能如下所示。Floyd的最短路徑算法C++

void floyd(const Graph<City>& g, double**& dist, int**& path) 
{ 
    int n = g.size(); 
    for (int i = 1; i <= n; i++) 
    { 
     for (int j = 1; j <= n; j++) 
     { 
      path[i][j]=0; 
      if (i==j) 
       dist[i][j]=0; 
      else if (!g.isEdge(i, j)) 
       dist[i][j]=INFINITY; 
      else 
       dist[i][j]=g.retrieveEdge(i, j); 
     } 
    } 
    for (int i = 1; i <= n; i++) 
    { 
     for (int j = 1; j <= n; j++) 
     { 
      for (int k = 1; k <= n; k++) 
      { 
       if ((dist[i][k]!=INFINITY) && (dist[k][j]!=INFINITY) && k!=i && k!=j && i!=j) 
       { 
        if ((dist[i][j]) > (dist[i][k]+dist[k][j])) 
        { 
         path[i][j]=k; 
         dist[i][j]=dist[i][k]+dist[k][j]; 
        } 
       } 
      } 
     } 
    } 
}

來源

2017-04-18 Rory

首先使用您的調試器查看代碼中與您設想的設計偏離的位置。其次，在C++中僞造基於1的數組是一個危險的遊戲 - 它可能導致逐個記憶覆蓋。 – PaulMcKenzie

使用基本1陣列只是在內存中造成了一些浪費的地方，我一定要警惕那裏的問題，但使用調試器我只能夠發現它必須是我如何覆蓋路徑[i] [j ]。它有時被不正確的值覆蓋，無論我做什麼，我都沒有看到爲什麼。 – Rory

如果值被「無理由」覆蓋，則基於1的陣列可能是其原因。同樣，使用基於1的數組是內存覆蓋的主要原因，或者在某些情況下，無意中使用元素0（其中元素0是垃圾值）（但不是非法內存訪問）。 – PaulMcKenzie

因此，如果有從頂點長最短路徑i到j，然後路徑[i] [j]應該等於連接至i的k值，而是它的k值連接到j和餘不能找出爲什麼。

不幸的是，兩者都沒有。有沒有在你的實現，保證了path[i][j]應該等於一個k值i後，立即來了，你的觀察是path[i][j]是目前我們能夠立刻之前j也是不正確的一個k值。（請多試幾個樣本來驗證的第二個點。）

由您實現保障的唯一的事情就是頂點path[i][j] == k在於某處從頂點i的最短路徑到頂點j。

因此，你可以通過做遞歸檢索路徑：

get_path(i, j): 
    k = path[i][j] 
    get_path(i, k) + k + get_path(k, j)

已經澄清說，there does exist a method在那裏你可以存儲path[i][j]，使得它是i後緊跟的頂點。

來源

2017-04-19 02:19:15 wookie919

Floyd的最短路徑算法C++

回答

相關問題