大哥别怪我！题目都挂了一天了，还没有见有大侠帮忙， 我想，是~ 不~是~我的标题有问题，于是呼，我就换了一个标题又发了上来， 目的只是能解决算法中存在的问题。 对我的行为向各位道歉，且先致以诚挚的谢意！！
这是一个寻求最短路径的函数 但是对图中的某些点不能搜索出最短路线 void shortpath(struct AlGraph G) { int cost[MAX][MAX]; /*cost[][]记录的是路径长度*/ int dist[MAX]; /*某源点到各顶点的最短路径长度,dist[k-1]为到所查询的景点的距离，最终只须输出该值 */ int path[MAX]; /*某源点到终点经过的顶点有序集短路径的终点判定集合,合的数组,即要输出的内容*/ int s[MAX]; /*最短为1则已经包含*/ int i,j,n,v0,min,u,k;/*u存放最短路径的终点,k记录所要查询的景点终点*/ int m1,m2; printf("\n请输入你要查询的景点起点的编号 :"); scanf("%d",&v0); if( v0<=0 || v0>G.vexnum ) { printf("\n 你的输入有错误！ \n"); exit(-1); } printf("请输入你要游览的景点代号 : "); scanf("%d",&k); if( k<=0 || k>G.vexnum ) { printf("\n 你的输入有错误！ \n"); exit(-1); } printf(" 请按回车键以继续\n"); getchar(); m1=v0; m2=k; v0--; k--; for(i=0;i<G.vexnum;i++) /*给cost[][]赋初始值*/ { for(j=0;j<G.vexnum;j++) cost[i][j]=G.arcs[i][j]; } printf(" 初始值赋值结束 \n"); getchar(); for(i=0;i<G.vexnum;i++) /* 所要景点到其他景点的路径长 */ { dist[i]=cost[v0][i]; if(dist[i]<large&&dist[i]>0) path[i]=v0; s[i]=0; } printf(" 路径求解结束 \n"); getchar(); clrscr(); s[v0]=1; /* 记录起始点 */ for(i=0;i<G.vexnum;i++) { min=large; u=v0; for(j=0;j<G.vexnum;j++) if(s[j]==0&&dist[j]<min) {min=dist[j];u=j;} s[u]=1; /*u顶点是求得最短路径的顶点编号,置1表示记录下*/ for(j=0;j<G.vexnum;j++) if(s[j]==0&&dist[u]+cost[u][j]<dist[j]) { dist[j]=dist[u]+cost[u][j]; path[j]=u; } } printf("输出 % s 到各个景点的距离 \n" ,name[m1-1]); for(i=0;i<G.vexnum;i++) if(i!=m1-1) printf(" %d米 \t %s \n\n",dist[i],name[i]); getchar(); printf("\n 顶点 %s 到 %s 的最短路径长度为和途径如下 :\n",name[m1-1],name[m2-1]);
getchar(); i=m1;/*输出结果*/ printf("%s\t",name[u]); if(s[i]==1) { u=i; while(u!=v0) { getchar(); printf("中间途经---%s ",name[u]); u=path[u]; } printf("\n 路径长度是%d米 ",dist[i]); printf(" \n 输出结束 \n"); getchar(); } }
附：图中有直接通路的初始值 G.arcs[0][1]=100; G.arcs[0][12]=200; G.arcs[1][0]=100; G.arcs[1][3]=120; G.arcs[1][6]=50; G.arcs[1][7]=50; G.arcs[1][12]=100; G.arcs[1][13]=50; G.arcs[2][3]=50; G.arcs[2][13]=30; G.arcs[3][1]=120; G.arcs[3][2]=50; G.arcs[3][4]=50; G.arcs[3][5]=50; G.arcs[3][6]=50; G.arcs[4][3]=50; G.arcs[4][5]=100; G.arcs[5][3]=50; G.arcs[5][4]=100; G.arcs[5][6]=50; G.arcs[5][8]=50; G.arcs[6][1]=50; G.arcs[6][3]=50; G.arcs[6][5]=50; G.arcs[6][7]=30; G.arcs[6][8]=50; G.arcs[6][9]=50; G.arcs[7][1]=50; G.arcs[7][6]=30; G.arcs[7][9]=50; G.arcs[8][5]=50; G.arcs[8][6]=80; G.arcs[9][6]=50; G.arcs[9][7]=50; G.arcs[9][10]=50; G.arcs[9][12]=50; G.arcs[10][9]=50; G.arcs[10][11]=50; G.arcs[10][12]=100; G.arcs[11][10]=50; G.arcs[12][0]=200; G.arcs[12][1]=100; G.arcs[12][9]=50; G.arcs[12][10]=100; G.arcs[13][1]=50; G.arcs[13][2]=30; 谢谢各位！
[此贴子已经被作者于2004-10-07 07:47:43编辑过]
