最短路径算法在交通中的运用

这是以前写的！！无论是有向图还是无向图都可以处理
！！用的是Dijkstra算法

/*求最短路径*/
#include
#include
typedef int Status;
typedef Status ** Node;
#define MaxNum 10000;
#define FALSE 0;
#define TRUE 1;

/*建一个带权的邻接矩阵来存放有向图*/
Node Build (Status num , Status num2 )
{
int i,j,k,h;
Node a;
a=(Node) malloc( num * sizeof (Status *));
printf("请输入图的相关信息,如0 2 10表示弧是从顶点v0走向顶点v2，且权为10\n");
printf("(每输入一个信息再按一次Enter)\n(在这里顶点是从v0算起，当然这并不是表示要从v0出发找最短路径\n");
printf("当然也可以从其他点出发找最短路径):\n");
for(i=0;i {
a[i]=(Status *) malloc( num * sizeof (Status));
for(j=0;j {
a[i][j]=MaxNum;
}
}
for(h=0;h {
scanf("%d %d %d",&i,&j,&k);
/*防止输入过界*/
if( i>=num || j>=num )
{
printf("无效的输入!请重新输入!!");
exit(1);
}
a[i][j]=k;
}
return a;
}

/*迪杰斯特拉算法求最短路径*/
void ShortestPath_DIJ( Node a ,Status i ,Status v0 ,Status *D ,Status *pre )
{
int v,w,j,l=1;
Status *final;/*final[v]为TRUE表示已经求得最短路径*/
Status min;

final=(Status *)malloc( sizeof(Status)*i );

for(v=0;v {
final[v]=FALSE;/*设空路径*/

pre[v]=FALSE;
D[v]=a[v0][v];

if(D[v]<10000)
pre[v]=v0;

}//for
/*选择的顶点没有出度时，为了防止下面的算法出现越界，直接输出，不再进行下步动作*/
for(v=0;v {
if( a[v0][v]==10000 )
l++;
}

if(l>i)
{
printf("\n从v%d出发没有最短路径到其他端点!\n",v0);
exit(0);
}
D[v0]=0; final[v0]=TRUE;//初始化,v0顶点确定
for( j=0 ; j {

/*找出距离顶点最近的顶点*/
min=MaxNum;
for( w=0 ; w {
if( !final[w] )//w顶点还没确定
{
if( D[w] {
v=w;min=D[w];/*w顶点离v0更近*/
//printf("wozaizhe");
}
}

}
final[v]=TRUE;

/*更新当前最短路径及距离*/
for( w=0 ; w {
if( !final[w] && ( (min+a[v][w]) {
D[w]=min+a[v][w];
pre[w]=v;
}//if
}

}//for
}//ShortestPath_DIJ

void Show(Status *D , Status *pre ,int i ,int v0)
{
int j,k,m,n;
int *temp;
temp=(int *)malloc(sizeof(int)*i);

for(j=0;j {
printf("\nv%d路径长度为:%d " ,j,D[j]);

n=j;
if(D[j]!=10000)
for(k=0;k {
temp[k]=pre[n];
if(temp[k]!=v0)
n=temp[k];

if(temp[k]==v0)
break;
}

if( k==0&&D[j]!=10000&&D[j]!=0 )
{
printf("v%d->v%d",v0,j);

}
if( k!=0 &&D[j]!=10000&&D[j]!=0)
{
for(m=k;m>=0;m--)
{
printf("v%d->",temp[m]);
}
printf("v%d",j);
}

if(D[j]==10000)
{
printf("从v%d出发没有最短路径!",v0);
}
if(D[j]==0)
{
printf("v%d",v0);
}

}
printf("\n");
}

main()
{
int i,j,v0;
Node a;
Status *D,*pre;

printf("请输入有向图的顶点数!");
scanf("%d",&i);

printf("再输入有向图的有效弧数!");
scanf("%d",&j);

D=(Status *)malloc(sizeof(Status)*i);
pre=(Status *)malloc(sizeof(Status)*i);

a=Build(i,j);

printf("请输入起始顶点(可以是范围内的任何顶点): ",j);
scanf("%d",&v0);
if(v0>i)
{
printf("输入错误!不存在这样的起始点!");
exit(1);
}

ShortestPath_DIJ( a ,i ,v0 ,D , pre );

Show( D, pre, i, v0 );

}