#include <stdio.h>
#include <stdlib.h>
//图节点
typedef struct VertexNode
{
char name;
int key;
VertexNode *p;
}Vertex,*pVertex;
//图
typedef struct
{
int vn;
int **E;
pVertex *V;
}Graph,*pGraph;
//根据算法导论 图24-4 初始化图
pGraph initGraph()
{
pGraph g=(pGraph)malloc(sizeof(Graph));
g->vn=5;
pVertex vs=(pVertex)malloc(sizeof(Vertex));
vs->name='s';
vs->key=0;
vs->p=NULL;
pVertex vt=(pVertex)malloc(sizeof(Vertex));
vt->name='t';
vt->key=INT_MAX;
vt->p=NULL;
pVertex vy=(pVertex)malloc(sizeof(Vertex));
vy->name='y';
vy->key=INT_MAX;
vy->p=NULL;
pVertex vx=(pVertex)malloc(sizeof(Vertex));
vx->name='x';
vx->key=INT_MAX;
vx->p=NULL;
pVertex vz=(pVertex)malloc(sizeof(Vertex));
vz->name='z';
vz->key=INT_MAX;
vz->p=NULL;
g->V=(pVertex*)malloc(g->vn*sizeof(pVertex));
g->V[0]=vs;
g->V[1]=vt;
g->V[2]=vy;
g->V[3]=vx;
g->V[4]=vz;
g->E = (int**)malloc(g->vn*sizeof(int*));
for(int i=0;i<g->vn;i++)
{
g->E[i]=(int*)malloc(g->vn*sizeof(int));
}
for(int i=0;i<g->vn;i++)
{
for(int j=0;j<g->vn;j++)
{
g->E[i][j]=INT_MAX;
}
}
g->E[0][1]=6;
g->E[0][2]=7;
g->E[1][2]=8;
g->E[1][3]=5;
g->E[1][4]=-4;
g->E[2][3]=-3;
g->E[2][4]=9;
g->E[3][1]=-2;
g->E[4][3]=7;
return g;
}
void relax(pGraph g,int u,int v)
{
//无边，不进行松弛
if(g->E[u][v]==INT_MAX)
return;
int sum,uk=g->V[u]->key,vk=g->V[v]->key,ew=g->E[u][v];
//根据规则，加上无穷等于无穷
if(uk==INT_MAX || ew==INT_MAX)
sum=INT_MAX;
else
sum=uk+ew;
if(vk>sum)
{
g->V[v]->key=sum;
g->V[v]->p=g->V[u];
}
}
bool BellmanFord(pGraph g)
{
for(int i=1;i<=g->vn-1;i++)
{
for(int j=0;j<g->vn;j++)
{
for(int k=0;k<g->vn;k++)
{
if(g->E[j][k]<INT_MAX)
relax(g,j,k);
}
}
}
for(int u=0;u<g->vn;u++)
{
for(int v=0;v<g->vn;v++)
{
if(g->E[u][v]>0)
{
int sum,uk=g->V[u]->key,vk=g->V[v]->key,ew=g->E[u][v];
//根据规则，加上无穷等于无穷
if(uk==INT_MAX || ew==INT_MAX)
sum=INT_MAX;
else
sum=uk+ew;
if(vk>sum)
return false;
}
}
}
return true;
}
void printKey(pGraph g)
{
for(int i=0;i<g->vn;i++)
{
pVertex v=g->V[i];
printf("%c %d\n",v->name,v->key);
}
}
void main()
{
pGraph g=initGraph();
bool b=BellmanFord(g);
if(b)
printKey(g);
else
printf("No Path!");
getchar();
}
