0
我對這段代碼有什麼問題一無所知。 它沒有按預期工作。其預期顯示從頂點1到N的最短路徑。 但它在許多情況下失敗。 一個這樣的情況下是它顯示了答案 1 25 -1 3 這是錯誤... 任何幫助,將不勝感激。 謝謝。我執行bellman-ford有什麼問題?
#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");
}
}
所以,其餘的代碼,算法,罰款? –
好吧,所以它的工作!謝謝!這麼愚蠢的我沒有想到這個! –