我执行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)