有向图邻接表 最短路径.doc

有向图最短距离

#include<stdio.h>
#defineINFINITY10000
#defineTRUE1
#defineFALSE0
#defineVERTEX_NUM6

typedefstructGraph
{
charvexs[VERTEX_NUM];
intarcs[VERTEX_NUM][VERTEX_NUM];
intvexnum;
intarcnum;
}Graph;

voidShortestPath(Graphg,intv0,intp[][VERTEX_NUM],intd[])
{

intv;
intw;
intmin;
inti,j;
intfinal[VERTEX_NUM];

for(v=0;v<g.vexnum;v++)
{
final[v]=FALSE;
d[v]=g.arcs[v0][v];
for(w=0;w<g.vexnum;w++)
{
p[v][w]=-1;
}
if(d[v]<INFINITY)
{
p[v][0]=v0;
p[v][1]=v;
}
}

d[v0]=0;
final[v0]=TRUE;

for(i=1;i<g.vexnum;i++)
{
min=INFINITY;
for(w=0;w<g.vexnum;w++)
{
if(!final[w])
{
if(d[w]<min)
{

v=w;
min=d[w];
}
}
}
final[v]=TRUE;
for(w=0;w<g.vexnum;w++)
{
if(!final[w]&&(min+g.arcs[v][w]<d[w]))
{

d[w]=min+g.arcs[v][w];
for(j=0;p[v][j]>-1&&j<VERTEX_NUM;j++)
{
p[w][j]=p[v][j];
}
p[w][j]=w;
}
}
}
}

voidmain()
{
inti,
j;
Graphg;
intp[VERTEX_NUM][VERTEX_NUM];
intd[VERTEX_NUM];
intv0;

g.vexs[0]='A',g.vexs[1]='B',g.vexs[2]='C',g.vexs[3]='D',g.vexs[4]='E',g.vexs[5]='F';
for(i=0;i<VERTEX_NUM;i++)
for(j=0;j<VERTEX_NUM;j++)
g.arcs[i][j]=INFINITY;
g.arcs[0][2]=10,g.arcs[0][4]=30,g.arcs[0][5]=100,g.arcs[1][2]=5,
g.arcs[2][3]=50,g.arcs[3][5]=10,g.arcs[4][3]=20,g.arcs[4][5]=60;
g.vexnum=g.arcnum=VERTEX_NUM;

for(i=0;i<VERTEX_NUM;i++)
{
printf("%c\t",g.vexs[i]);
for(j=0;j<VERTEX_NUM;j++)
{
printf("]",g.arcs[i][j]);
}
printf("\n");
}
printf("\n");

v0=0;
ShortestPath(g,v0,p,d);

for(i=0;i<g.vexnum;i++)
{
printf("Path%cto%c:\n",g.vexs[v0],g.vexs[i]);
if(p[i][v0]!=-1)
{
for(j=0;p[i][j]!=-1;j++)
{
if(j!=0)
printf("→");
printf("%c",g.vexs[p[i][j]]);
}
printf("\n");
}
printf("Length:%d\n",d[i]);
printf("\n");
}
}