bellman_ford.txt

图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!

#include <stdio.h>
#define N 101
#define M 1<<30

struct points
{
 int road[N];
 int len[N];
 int num;
}point[N]={0};

struct line
{
 int u;
 int v;
 int w;
};

int n,k;
line m[N*N]={0};

bool bellman_ford(int first)
{
 int t,i,j,u,v,w;
 int dist[N]={0},pre[N]={0};
 
 for(i=1;i<=n;i++) dist[i]=pre[i]=M;
 dist[first]=0;pre[first]=-1;

 for(t=1;t<n;t++)
 {
  for(i=1;i<=n;i++)
  {
   for(j=0;j<point[i].num;j++)
   {
    u=i;v=point[i].road[j];w=point[i].len[j];
	if(dist[v]>dist[u]+w) {dist[v]=dist[u]+w; pre[v]=u;}
   }
  }
 }

 for(i=1;i<=n;i++)
 {
  for(j=0;j<point[i].num;j++)
  {
   u=i;v=point[i].road[j];w=point[i].len[j];
   if(dist[v]>dist[u]+w) return false;
  }
 }

 for(i=1;i<=n;i++) printf("pre:%d  dist:%d\n",pre[i],dist[i]);
 return true;
}

int main()
{
 int i,a,b,c;
 scanf("%d %d",&n,&k);
 for(i=1;i<=k;i++) 
 {
  scanf("%d %d %d",&a,&b,&c);
  point[a].road[point[a].num]=b;
  point[a].len[point[a].num]=c;
  point[a].num++;
 }
 printf("\n%d\n",bellman_ford(1));
 scanf("%d",&i);
}