Bellman－Ford算法 最短路径

本文主要是介绍Bellman－Ford算法 最短路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 1 #include <bits/stdc++.h>
 2 const int INF=99999;
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int dis[105] , i , k , n , m , u[105] , v[105] , w[105];
 8      bool flag=false;
 9      cin>>n>>m;
10      for(int i=1;i<=m;i++)
11      {
12          cin>>u[i]>>v[i]>>w[i];     //分别为i点 j点  i到j 的距离
13      }
14    for(i = 1;i <= n;i++)
15           dis[i] = INF;
16     dis[1]=0;
17     for(int k=1;k<=n;k++)  //k次循环，松弛k次
18     {
19         for(int i=1;i<=m;i++)
20         {
21             if(dis[v[i]]>dis[u[i]]+w[i])
22                 dis[v[i]]=dis[u[i]]+w[i];
23         }
24     }
25     for(int i=1;i<=m;i++)   //此处的感觉有点类似找环的意思
26     {
27          if(dis[v[i]]>dis[u[i]]+w[i])
28             flag=true;
29     }
30 if(!flag)
31    {
32         for(int i=1;i<=n;i++)
33 {
34     cout<<dis[i]<<' ';
35 }
36    }
37 else
38 {
39     cout<<"存在负环"<<endl;
40 }
41 
42 }

这篇关于Bellman－Ford算法 最短路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！