数据结构 最短路径.doc

include
#define number 5
#define infinit 1000
struct Graph
{ char vexs[number];
int arcs[number][number];
int vexnum;
int arcnum;
}; struct Graph G;
void ShortestPath(Graph G,int p[number][number][number],int d[number][number])
{
int v,w,u,i;

for(v=0;v for (w=0;w else
p[v][w][i] = p[u][w][i];
}
}}
void Print ( Graph G, int p[number][number][number],int d[number][number] )
{
int i,j,k;
printf("路径对照\n0--A\n1--B\n2--C\n3--D\n4--E\n");
printf("请输入起始点和终点\n");
scanf("%d,%d",&i,&j);
printf("路径由 %c 到 %c 是:\n",G.vexs[i],G.vexs[j]);
if ( p[i][j][i] ==0) printf("没有能够到达的路径！\n");
else
{ k = i;
while( k != 0)
{
if (k != i)
printf("-->");
printf("%c",G.vexs[k]);
k = p[i][j][k];
}
printf("\n");
printf("路径长度为:%d\n",d[i][j]);
printf("\n");
}}
void main()
{
int i,j,a,b,w;
Graph G;
int p[number][number][number];
int d[number][number];
G.vexs[0]='A',G.vexs[1]='B',G.vexs[2]='C',G.vexs[3]='D',G.vexs[4]='E';//暂按5个点输出
for(i = 0;i arcs[i][j]=0;
else G.arcs[i][j]=infinit;
}
printf("请输入有实际权值的弧数\n");
scanf("%d",&G.arcnum);
for(i = 0;i