Bellman-Ford算法

解决负权边
    //假设1号顶点为源点 
    核心算法:

for(int k=1;k<=n-1;k++) //进行n-1轮松弛 
		for(int i=1;i<=m;i++) //枚举每一条边 
			if( dis[ v[i] ] > dis[ u[i] ] + w[i] ) //尝试对每一条边进行松弛 
				dis[ v[i] ] = dis[ u[i] ] + w[i]; 

    //dis数组-->记录源点到其余各个顶点的最短路径
    //u,v和w三个数组 -->记录边的信息
        例如 第i条边存储在u[i],v[i],w[i]中
            表示 顶点u[i]到顶点v[i]这条边，权值为w[i] 
                 即 u[i] --> v[i] 权值为w[i] 

    if( dis[ v[i] ] > dis[ u[i] ] + w[i] )
        dis[ v[i] ] = dis[ u[i] ] + w[i]; 
    //看看能否通过u[i]-->v[i](权值为w[i])这条边，使得1号
      顶点到v[i]号顶点的距离变短
    
    若要把所有的边都松弛一遍

	for(int i=1;i<=m;i++)
		if( dis[ v[i] ] > dis[ u[i] ] + w[i] )
			dis[ v[i] ] = dis[ u[i] ] + w[i];  

    例如：
        input u[] v[] w[]  u[i]-->v[i]
        i=1      2   3   2
        i=2      1   2   -3
        i=3      1   5   5
        i=4      4   5   2
        i=5      3   4   3
    初始化： dis数组存放1号顶点到所有顶点的距离 
              1    2    3     4     5
        dis: 0   INF INF INF INF
    第一轮松弛(从源点带入input数据) 
             1     2    3     4    5
        dis: 0   -3  INF INF 5
    第二轮松弛(从源点出发到已经不是INF的点 继续带入input数据) 
              1    2    3   4   5
        dis: 0   -3  -1   2   5
    第三轮松弛 
              1    2    3   4   5
        dis: 0   -3  -1   2   4
    第四轮松弛
               1   2   3   4   5
        dis: 0   -3  -1  2   4
    
    最多需要n-1轮即可完成，因为在一个包含n个顶点的图中，任意两点之间的最短
    路径最多包含n-1边，不会存在回路，无论是正权回路还是负权回路     

完整的代码如下：

#include<stdio.h>
int main(){
	int dis[10];
	int i,k;
	int n,m,u[10],v[10],w[10];
	int INF = 99999999;
	scanf("%d%d",&n,&m);
	
	//读入边 
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
	
	//初始化dis数组，这里是1号顶点到其余各个顶点的起始路程
	for(i=1;i<=n;i++)
		dis[i]=INF;
	dis[1]=0; 
	
	/*
	//Bellman-Ford算法核心语句
	for(k=1;k<n-1;k++)
		for(i=1;i<=m;i++)
			if( dis[v[i]]>dis[u[i]]+w[i])
				dis[v[i]]=dis[u[i]]+w[i];
	*/
	//Bellman-Ford算法改良版
	//可以检查是否完成，可以提前跳出循环 
	for(k=1;k<=n-1;k++){
		int check=0; //用来标记在本轮松弛中数组dis是否会发生更新
		//进行一轮松弛
		for(i=1;i<=m;i++){
			if( dis[v[i]]>dis[u[i]]+w[i]){
				dis[v[i]]=dis[u[i]]+w[i];
				check = 1;//数组dis发生更新，改变check的值 
			}
		} 
		//松弛完毕后检测数组dis是否有更新
		if(check==0) break;//若数组dis没有更新，提前退出循环 
		
	}
	
	//检测负权回路	
	int flag = 0;  
	for(i=1;i<=m;i++)
		if(dis[v[i]] > dis[u[i]] + w[i])
			flag = 1;
	if(flag==1) 
		printf("此图含有负权回路");
	
	 
	//输出最终结果
	for(i=1;i<=n;i++)
		printf("%d ",dis[i]);
	
	getchar(); getchar();
	return 0; 	
}