Bellman-Ford（边权可正可负）

Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。

在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含n-1 条边，所以，只需要循环n-1 次。

如果最短路存在，则一定不含环：

1.存在零环或正环，则去掉环路径不会变长

2.存在负环，则只要绕着环走，路径只会越来越短，下界不收敛，不存在最短路

最短路只包含n-1个结点（不包含起点）

操作步骤：

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。

第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
d（v） > d (u) + w(u,v)说明无法向下收敛

#include
  
   
#include
   
     #include
    
      using namespace std; #define inf 0x7ffffff struct Edge { int u,v,cost; }edge[2000]; int pre[200];//父亲 int dis[200];//到源点的距离 int n,m,src;//点的个数，边数，源点 bool relax(int u,int v,int cost)//对边进行松弛 { if(dis[v]>dis[u]+cost) { dis[v]=dis[u]+cost; return true;//成功松弛 } return false;//没有松弛成功 } int Bellman_Ford() { int i,j,flag; for(i=1;i<=n;i++) dis[i]=(i==src? 0:inf);//第一步：初始化dis for(i=1;i
     
      输入案例1.
      
 4 6 1
      
 1 2 20
      
 1 3 5
      
 4 1 -200
      
 2 4 4
      
 4 2 4
      
 3 4 2
      
 
      
 
      
 
      
 输入案例2.
      
 4 6 1
      
 1 2 2
      
 1 3 5
      
 4 1 10
      
 2 4 4
      
 4 2 4
      
 3 4 2