我对这段代码有什么问题一无所知。它没有按预期工作。它预计会显示从顶点 1 到 N 的最短路径。但它在很多情况下都失败了。一个这样的情况是 3 1 1 2 1 它显示答案为 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");
}
}