数据结构程序求有向图的最短路径.doc

/*求有向图的最短路径*/
#include<stdio.h>
#definen5
#definee7
typedefintvextype;
typedefintadjtype;
typedefstruct
{
vextypevexs[n];
adjtypearcs[n][n];
}graph;
graph*ga;
/*建立*/
creatgraph()
{
inti,j,k,w;
printf("Pleaseinput:\n");
for(i=0;i<n;i++)
scanf("%d",&ga->vexs[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ga->arcs[i][j]=1000;
printf("Pleaseinput:\n");
for(k=0;k<e;k++)
{
scanf("%d%d%d",&i,&j,&w);
ga->arcs[i-1][j-1]=w;
}
printf("Theresultis:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d\t",ga->arcs[i][j]);
printf("\n");
}
}
/*求最短路径*/
DIJKSTRA()
{
intP[n],S[n],D[n];
inti,j,k,vl=0,pre;
intmin,max=1000,inf=8000;
for(i=0;i<n;i++)
{
D[i]=ga->arcs[vl][i];
if(D[i]!=max)
P[i]=1;
else
P[i]=0;
}
for(i=0;i<n;i++)
S[i]=0;
S[vl]=1;
D[vl]=0;
for(i=0;i<n-1;i++)
{
min=inf;
for(j=0;j<n;j++)
if((!S[j])&&(D[j]<min))
{
min=D[j];
k=j;
}
S[k]=1;
for(j=0;j<n;j++)
if((!S[j]&&D[j]>D[k]+ga->arcs[k][j]))
{
D[j]=D[k]+ga->arcs[k][j];
P[j]=k+1;
}
}
printf("lengthlujing\n");
for(i=0;i<n;i++)
{

printf("%d\t%d",D[i],i+1);
pre=P[i];
while(pre!=0)
{
printf("<--%d",pre);
pre=P[pre-1];
}
printf("\n");
}
}
/*主函数*/
voidmain()
{
creatgraph();
printf("Dijkstra:\n");
DIJKSTRA();
getch();
}
运行结果为：