最短路径问题.txt

最短路径问题

发件人: "d_ljuan" <[e-mail]>
收件人: <[e-mail]>
主题: 程序
日期: 2004年12月5日 18:27

#include<stdio.h>
#include<string.h>
#define infinity 1000
#define maxsize 6
#define false 0
#define true 1
typedef struct{
int vex[maxsize];
int arcs[maxsize][maxsize];
int vexnum,arcnum;
}mgraph;
void shortestpath_dij(mgraph g,int m,char p[][6],int d[],int a[])
{int w,v,i,j,min,k=0;
 int final[maxsize];
 for(v=0;v<g.vexnum;++v)
 {final[v]=false;
  d[v]=g.arcs[m][v];
  if(d[v]<infinity)
   {p[v][m]=true;
    p[v][v]=true;
   }
  }
  d[m]=0;
final[m]=true;
a[k]=m;
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];
    }
   if(!final[v])
   {final[v]=true;
   a[++k]=v;
   }
   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;j<6;j++)
     p[w][j]=p[v][j]; 
     p[w][w]=true;
    }
}
}
printshortpath(char p[][6],int a[],int d[],int n,int m)
{int k;
 printf("\nv%d到v%d的最短路径为:",m,n);
 for(k=0;a[k]!=6;k++)
 if(p[n][a[k]]==true)
 printf("v%d",a[k]);
 if(d[n]==infinity)
 printf("\n无路径!");
 else
 printf("\n最短长度为：%d",d[n]);
}
main()
{mgraph g;
 int m,v,w,i,j;
char x;
int a[maxsize],d[maxsize];
char p[maxsize][maxsize];
int v0=0,v1=1,v2=2,v3=3,v4=4,v5=5;
g.vexnum=6;
for(i=0;i<6;i++)
a[i]=6;
for(v=0;v<maxsize;v++)
for(w=0;w<maxsize;w++)
{g.arcs[v][w]=infinity;
 p[v][w]=false;
}
g.arcs[v0][v2]=10;
g.arcs[v0][v4]=30;
g.arcs[v0][v5]=100; 
g.arcs[v1][v2]=5;
g.arcs[v2][v3]=50;
g.arcs[v3][v5]=10;
g.arcs[v4][v3]=20;
g.arcs[v4][v5]=60;
printf("1.求v0到其余各顶点的最短路径长度及每一条路径所经过的顶点.\n");
printf("2.是输出任意两顶点的最短路径长度及每一条路径所经过的顶点.\n");
printf("若选择1，则请输入1;\n");
printf("若选择2，则请输入2.\n");
x=getchar(); 
if(x=='1')
{m=v0;
 shortestpath_dij(g,m,p,d,a);
 for(j=1;j<6;j++)
 printshortpath(p,a,d,j,m);
}
else if(x=='2')
{printf("你想求哪两个顶点之间的最短路径？请输入\n");
 scanf("%d %d",&m,&j);
 shortestpath_dij(g,m,p,d,a);
 printshortpath(p,a,d,j,m);
}
}