bellman_ford.c

来自「一个简单的Bellman_and_Wallshall算法的实现。只是和大家交流一」· C语言 代码 · 共 61 行

#include<stdio.h>

#define max 5000;
#define NIL 00;

struct edge
{
	int start;
	int end;
	int weight;
};

main()
{
	int i;
	int num;
	int d[5];
	int p[5];
	struct edge gra[5];
	for(i=0;i<5;i++)
	{
		d[i]=max;
		p[i]=NIL;
	}
	d[0]=0;//该图的原点即为0点
	for(i=0;i<5;i++)
		gra[i].start=gra[i].end=gra[i].weight=0;
	printf("\n  请注意！本程序可以处理5条边的有向图\n");
	printf("\n  （程序默认所输入的第一个点为图的原点）\n");
	printf("\n  请输入图中结点的个数:");
	scanf("%d",&num);
	printf("\n  请按照：起始点，权值，终止点的顺序输入图的信息\n");
	for(i=0;i<5;i++)
		scanf("%d%d%d",&gra[i].start,&gra[i].weight,&gra[i].end);
	for(i=0;i<5;i++)
	{
		if(d[gra[i].end]>d[gra[i].start]+gra[i].weight)
		{
			d[gra[i].end]=d[gra[i].start]+gra[i].weight;
			p[gra[i].end]=gra[i].start;
		}
	}
	for(i=0;i<5;i++)
	{
		if(d[gra[i].end]>d[gra[i].start]+gra[i].weight)
		{
			printf("\n  图的数据不合适，第%d条边处出现了负环，请仔细检查！\n",i);
			main();
			exit(0);
		}
	}
	for(i=0;i<num;i++)
	{
		printf("  原点到第%d个结点的最短路径的值是%d\n",i,d[i]);
		//if(!p[i]==0)
		//	printf("路径是%d",p[i]);
	}
}