Bellman - Ford

The Bellman - Ford algorithm is a classical graph algorithm. It can calculate the shortest path and is often used for negative cycle detection. The Bellman - Ford proceeds by relaxation just like the Dijkstra's algorithm. We can say that Bellman - Ford uses Dynamic Programming technique. Bellman - Ford runs in O(V*E).

C++ code

#include <bits/stdc++.h>
using namespace std;

int main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n,a;
   cin >> n >> a;
   vector<tuple<int,int,int>> adj;
   for (int i=0; i<a; ++i){
       int inter1,inter2,dist;
       cin >> inter1 >> inter2 >> dist;
      adj.emplace_back(make_tuple(inter1,inter2,dist));
   }
   vector ret(n+1,10000000);
   ret[1] = 0;
   for (int i=1; i<n; ++i){
      for (auto& e:adj){
         int a,b,w;
         tie(a,b,w) = e;
         ret[b] = min(ret[b],ret[a]+w);
      }
   }
   int ab=ret[n];
   for (auto& e:adj){
      int a,b,w;
      tie(a,b,w) = e;
      ret[b] = min(ret[b],ret[a]+w);
   }
   if (ab == ret[n]) cout << ret[n];
   else cout << "ERREUR";
   return 0;
}