Floyd-Warshall算法的路徑重建對於某些值不起作用

我實現了像那樣的算法http://en.algoritmy.net/article/45708/Floyd-Warshall-algorithm。Floyd-Warshall算法的路徑重建對於某些值不起作用

void Graph::floydWarshal() 
{ 
for (int k = 0; k < weight_matrix.size(); k++) 
{ 
    for (int i = 0; i < weight_matrix.size(); i++) 
    { 
     for (int j = 0; j < weight_matrix.size(); j++) 
     { 
      if (weight_matrix[i][k] != infinity && weight_matrix[k][j] != infinity) 
      { 
       int temp = weight_matrix[i][k] + weight_matrix[k][j]; 
       if (weight_matrix[i][j] > temp) 
       { 
        weight_matrix[i][j] = temp; 
        predecessors[i][j] = predecessors[k][j]; 
       } 
      } 
     } 
    } 
} 
} 

void Graph::getPath(int start, int finish, std::vector<int> &path) 
{ 
    if (start == finish) 
    { 
     path.push_back(start); 
    } 
    else if (predecessors[start][finish] == 0) 
    { 
     path.clear(); 
     return; 
    } 
    else 
    { 
     getPath(start, this->predecessors[start][finish], path); 
     path.push_back(finish); 
    } 
}

在構造函數來初始化前輩

for (int i = 0; i < weight_matrix.size(); i++) 
    { 
    for (int j = 0; j < weight_matrix[i].size(); j++) 
    { 
     if (weight_matrix[i][j] != 0 && weight_matrix[i][j] != infinity) 
     { 
      predecessors[i][j] = i; 
     } 
     else 
     { 
      predecessors[i][j] = -1; 
     } 
    } 
}

這是長度的矩陣

0 2 1 4 inf inf 
2 0 7 3 inf inf 
1 i 0 5 10 4 
4 7 5 0 inf 5 
inf 3 10 inf 0 4 
inf inf 4 5 4 0

它只能用於某些值，例如路徑從頂點5至頂點0構建（返回5 2 0）。但從0到5不能建立（返回5）。長度的矩陣建立正確

來源

2016-05-13 Sergey Kunitsyn

注以後，困惑的讀者：矩陣已被編輯，使其*爲*現在廣場。 –

爲什麼不使用調試器來跟蹤代碼，以查看它與算法的偏差？ – PaulMcKenzie

我認爲這個問題是在這條線（其中尋找一個不可能的路徑）：

else if (predecessors[start][finish] == 0)

你的節點從0開始索引，所以前身可以合法等於0 當路由包含節點零，你將錯誤地清除路徑。

嘗試使用這個：

else if (predecessors[start][finish] == -1)

來源

2016-05-13 21:02:07

Floyd-Warshall算法的路徑重建對於某些值不起作用

回答

相關問題