#include "stdio.h"
#define MAXNUM 7
#define INFINITY 32535
int graph[MAXNUM][MAXNUM]={{INFINITY,5,INFINITY,7,3,INFINITY,INFINITY},
{5,INFINITY,10,INFINITY,INFINITY,INFINITY,INFINITY},
{INFINITY,10,INFINITY,INFINITY,4,INFINITY,INFINITY},
{7,INFINITY,INFINITY,INFINITY,INFINITY,7,INFINITY},
{3,INFINITY,4,INFINITY,INFINITY,2,INFINITY},
{INFINITY,INFINITY,INFINITY,7,2,INFINITY,1},
{INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,1,INFINITY}};
int p[MAXNUM];
int d[MAXNUM];
void graph_init()
{
}
shortestpath(int v0)
{
int temp,temp1,temp2,final[MAXNUM],min,v;
for(temp=0;temp<MAXNUM;++temp)
{
final[temp]=0;d[temp]=graph[v0][temp];
if(d[temp]<INFINITY)
p[temp]=temp;
else
p[temp]=INFINITY;
}
p[v0]=v0;
d[v0]=0;
for(temp=0;temp<MAXNUM;temp++)
{
min=INFINITY;
for(temp1=0;temp1<MAXNUM;temp1++)
if(!final[temp1])
if(d[temp1]<min)
{
min=d[temp1];v=temp1;
}
final[v]=1;
for(temp1=0;temp1<MAXNUM;temp1++)
if(!final[temp1]&&(min+graph[v][temp1]<d[temp1]))
{
d[temp1]=min+graph[v][temp1];
p[temp1]=p[v];
}
}
}
showrout()
{
int temp;
printf("\nthe routing table is:\n");
for(temp=0;temp<MAXNUM;temp++)
printf("\n%c--%c--%d\n",temp+65,p[temp]+65,d[temp]);
}
main()
{
graph_init();
shortestpath(6);
showrout();
}
评论0