我執行bellman-ford有什麼問題？

Question

我對這段代碼有什麼問題一無所知。 它沒有按預期工作。其預期顯示從頂點1到N的最短路徑。 但它在許多情況下失敗。 一個這樣的情況下是它顯示了答案 1 25 -1 3 這是錯誤... 任何幫助，將不勝感激。 謝謝。

#include <iostream> 
#include <cstdio> 
#include <vector> 
#include <list> 
using namespace std; 

struct Edge{ 
    int I, W; 
}; 

vector <int> dist; 
vector <int> parent; 
bool bellman_ford(const vector< vector <Edge> > &graph, int n){ 
    dist[1] = 0; 
    parent[1] = 0; 
    for(int k = 1; k <= n-1; k++){ 
     for(int i = 1; i <= n; i++){ 
      int len = graph[i].size(); 
      for(int j = 0; j < len; j++){ 
       int v = graph[i][j].I; 
       int w = graph[i][j].W; 
       if(dist[v] > dist[i] + w){ 
        dist[v] = dist[i] + w; 
        parent[v] = i; 
       } 
      } 
     } 
    } 
    for(int i = 1; i <= n; i++){ 
     int len = graph[i].size(); 
     for(int j = 0; j < len; j++){ 
      int v = graph[i][j].I; 
      int w = graph[i][j].W; 
      if(dist[v] > dist[i] + w){ 
       return false; 
      } 
     } 
    } 
    return true; 
} 

int main(void){ 
    int n, m, x, y, w; 
    scanf("%d%d", &n, &m); 
    dist.resize(n+1, 10000000); 
    parent.resize(n+1, -1); 
    vector < vector <Edge> > graph (n+1, vector <Edge> (0)) ; 
    for(int i = 0; i < m; i++){ 
     scanf("%d%d%d", &x, &y, &w); 
     Edge a, b; 
     a.I = y; 
     b.I = x; 
     a.W = b.W = w; 
     graph[x].push_back(a); 
     graph[y].push_back(b); 
    } 
    if(bellman_ford(graph, n)){ 
     int k = n; 
     vector<int>ans; 
     ans.push_back(n); 
     while(parent[k] != 0){ 
      ans.push_back(parent[k]); 
      k = parent[k]; 
     } 
     for(int i = ans.size()-1; i >= 0; i--){ 
      printf("%d ", ans[i]); 
     } 
     printf("\n"); 
    } 
} 

Answer 1

對於3 1 1 2 1你有3個頂點的曲線圖將輸入的情況下，但該圖僅具有單個邊緣（1->2）：

(1)<~~>(2) (3) 

所以頂點編號3（n）從未達到。 3的父節點設置爲初始值-1，您的循環搜索0。你沒有檢查從源到目標的路徑，還是根本沒有。輸出是正確的，直到-1：

3 - target 
-1 - target has no parent, the loop should stop 
25 - *garbage* (UB) 
1 - *garbage* (UB)