Что случилось с моей реализацией 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)