该算法详解请看 https://www.cnblogs.com/tanky_woo/archive/2011/01/17/1937728.html
单源最短路 当图中存在负权边时 迪杰斯特拉就不能用了 该算法解决了此问题 时间复杂度O(nm)
注意 图中含有负圈时不成立。当判定存在负圈时，这只说明s可以到达一个负圈，并不代表s到每个点的最短路都不存在。
另外，如果图中有其他负圈但是s无法达到这个负圈，该算法也无法找到，解决方法加一个节点（还不会。。。）
该算法可以用 队列 优化 名为spfa
下面给出 有向图 的代码
1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 #include <stdlib.h> 5 #include <iostream> 6 #include <sstream> 7 #include <algorithm> 8 #include <string> 9 #include <queue> 10 #include <ctime> 11 #include <vector> 12 using namespace std; 13 const int maxn= 1e3+5; 14 const int maxm= 1e3+5; 15 const int inf = 0x3f3f3f3f; 16 typedef long long ll; 17 int n,m,s; //n m s 分别表示 点数-标号从1开始 边数-标号从0开始 起点 18 struct edge 19 { 20 int u,v,w; //u为边的起点 v为边的终点 w为边的权值 21 }edges[maxm]; 22 int d[maxn]; //d[i]表示 i 点到源点 s 的最短距离 23 int p[maxn]; //p[i]记录最短路到达 i 之前的节点 24 int Bellman_Ford(int x) 25 { 26 for(int i=1;i<=n;i++) 27 d[i]=inf; 28 d[x]=0; 29 for(int i=1;i<n;i++) // n-1次迭代 30 for(int j=0;j<m;j++) // 检查每条边 31 { 32 if(d[edges[j].u]+edges[j].w<d[edges[j].v]) // 松弛操作 33 { 34 d[edges[j].v]=d[edges[j].u]+edges[j].w; 35 p[edges[j].v]=edges[j].u; //记录路径 36 } 37 } 38 int flag=1; 39 for(int i=0;i<m;i++) //判断是否有负环 40 if(d[edges[i].u]+edges[i].w<d[edges[i].v]) 41 { 42 flag=0; 43 break; 44 } 45 return flag; //返回最短路是否存在 46 } 47 void Print_Path(int x) 48 { 49 while(x!=p[x]) //逆序输出 正序的话用栈处理一下就好了 50 { 51 printf("%d ",x); 52 x=p[x]; 53 } 54 printf("%d ",x); 55 } 56 int main() 57 { 58 while(scanf("%d %d %d",&n,&m,&s)!=EOF) 59 { 60 for(int i=0;i<m;i++) 61 scanf("%d %d %d",&edges[i].u,&edges[i].v,&edges[i].w); 62 p[s]=s; 63 if(Bellman_Ford(s)==1) 64 for(int i=1;i<=n;i++) 65 { 66 printf("%d %d ",i,d[i]); 67 Print_Path(i); 68 } 69 else 70 printf("sorry "); 71 return 0; 72 } 73 }
输入
6 9 1
1 2 2
1 4 -1
1 3 1
3 4 2
4 2 1
3 6 3
4 6 3
6 5 1
2 5 -1
输出
1 0
1
2 0
2 4 1
3 1
3 1
4 -1
4 1
5 -1
5 2 4 1
6 2
6 4 1
太菜了 wa~~