最短路径之Bellman-Ford算法

第一行为源点个数，边的个数m

接下来m行为a->b和权值

5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3

Bellman-Ford算法（1）：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define inf 1000000000

 using namespace std;

 int main()

 {

     int dis[], u[], v[], w[];

     int n, m;

     cin >> n >> m;

     for (int i = ; i <= m; i++)

         cin >> u[i] >> v[i] >> w[i];

     for (int i = ; i <= n; i++)

         dis[i] = inf;

     dis[] = ;

     for (int k = ; k < n; k++)

         for (int i = ; i <= m; i++)

             dis[v[i]] = min(dis[v[i]], dis[u[i]] + w[i]);

     for (int i = ; i <= n; i++)

         cout << dis[i] << " ";

     return ;

 }

（2）

 #include<iostream>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define inf 1000000000

 struct  edge

 {

     int from, to, cost;

 };

 edge es[];

 int d[], V, E;

 void path(int s)

 {

     for (int i = ; i <= V; i++) d[i] = inf;

     d[s] = ;

     while (true)

     {

         bool update = false;

         for (int i = ; i < E; i++)

         {

             edge e = es[i];

             if (d[e.from] != inf&& d[e.to]>d[e.from] + e.cost)

             {

                 d[e.to] = d[e.from] + e.cost;

                 update = true;

             }

         }

         if (!update) break;

     }

     for (int i = ; i <= V; i++)

         cout << d[i] << " ";

 }

 int main()

 {

     cin >> V >> E;

     for (int i = ; i < E; i++)

     {

         cin >> es[i].from >> es[i].to >> es[i].cost;

     }

     path();

     return ;

 }