解决负权边的算法(Bellman Ford )(有向图) (1)C ~

这个能够判断是否有负权边，但是不能计算有负圈的图，也就是说可以有负的权边，但是不能含有负权的环。

适用条件：

1.单源最短路径(从源点s到其它所有顶点v);

2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);（如1 2  -3, 2 1 -3 两次输入 无向图）

3.边权可正可负(如有负权回路输出错误提示);

核心代码：

int bellman_ford()
	{
		for(int i = 1; i <= n-1; i++ ){
			for(int j = 1; j <= m; j++ ){
				if(dist[edge[j].v] > dist[edge[j].u] + edge[j].w)
					{
						dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
						pre[edge[j].v] = edge[j].u;
					}
			}
		}
		int flag = 0;//判断有无负值圈
		for(int j = 1; j <= m; j++ ){
			if(dist[edge[j].v] > dist[edge[j].u] + edge[j].w){
				flag = 1;
			}
		}
		return flag;
	}

完整实现：

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define INF 65535
int n, m;
int dist[MAX], pre[MAX];
typedef struct Edge{
	int u;
	int v;
	int w;
}Edge;
Edge edge[MAX];

int bellman_ford()
	{
		for(int i = 1; i <= n-1; i++ ){
			for(int j = 1; j <= m; j++ ){
				if(dist[edge[j].v] > dist[edge[j].u] + edge[j].w)
					{
						dist[edge[j].v] = dist[edge[j].u] + edge[j].w;
						pre[edge[j].v] = edge[j].u;
					}
			}
		}
		int flag = 0;
		for(int j = 1; j <= m; j++ ){
			if(dist[edge[j].v] > dist[edge[j].u] + edge[j].w){
				flag = 1;
			}
		}
		return flag;
	}
void print_path(int root)
	{
		if(pre[root] != -1){
			print_path(pre[root]);
			printf("->");
		}
		printf("%d",root);
	}	
int main()
	{
		scanf("%d%d",&n, &m);
		for(int i = 1; i <= n; i++ ){
			dist[i] = INF;
			pre[i] = -1;
		}
		dist[1] = 0;//以从顶点1开始为例
		for(int j = 1; j <= m; j++ ){//输入边信息 
			scanf("%d%d%d",&edge[j].u, &edge[j].v, &edge[j].w);
		}
		printf("\n"); 
		if(!bellman_ford()){
			for(int i = 1; i <= n; i++ ){
			if(dist[i] != INF){
				print_path(i);//打印路径
				printf("  distance = %d\n",dist[i]); 
				printf("\n");
				}
			}
		}
		else
			printf("有负值圈.");			
	}