数据结构 最短路径.doc

#include <stdio.h>
#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<G.vexnum;v++)
for (w=0;w<G.vexnum;w++)
{
d[v][w]=G.arcs[v][w];
for (u=0;u<G.vexnum;u++)
p[v][w][u] = 0;
if (d[v][w]<infinit)
p[v][w][v] = w;
}
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for (w=0;w<G.vexnum;w++)
if (d[v][u]+d[u][w]<d[v][w])
{
d[v][w]=d[v][u]+d[u][w];
for (i=0;i<G.vexnum;i++)
{ if (p[v][u][i] != 0)
p[v][w][i] = p[v][u][i];
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 <number;i++)
for(j = 0;j <number;j++)
{
if(i==j) G.arcs[i][j]=0;
else G.arcs[i][j]=infinit;
}
printf("请输入有实际权值的弧数\n");
scanf("%d",&G.arcnum);
for(i = 0;i <G.arcnum;i++)
{ printf("依次输入弧尾、弧头，权值\n");
scanf("%d %d %d", &a, &b, &w);//a和b代表这条边的两个顶点，w代表两个点的权值
G.arcs[a][b] = w;}
G.vexnum=number;
printf("--------------------\n");
printf(" A B C D E\n");
for(i=0;i<number;i++)
{printf("%c ",G.vexs[i]);
for(j=0;j<number;j++)
printf("%3d ",G.arcs[i][j]);
printf("\n");
}
printf("--------------------\n");
ShortestPath(G,p,d);
Print(G,p,d);
}