dist[v0] = 0;
s[v0] = 1;//源节点作为最初的s子集 for (i = 1; i < g.N; i++) {
int temp = maxint;
int u = v0;
//加入具有最小代价的邻居节点到s子集 for (j = 1; j <=g.N; j++) {
if ((!s[j]) && (dist[j] < temp)) {
u = j;
temp = dist[j]; } }
s[u] = 1;
//计算加入新的节点后，更新路径使得其产生代价最短 for (j = 1; j <=g.N; j++) {
if ((!s[j]) && (g.edge[u][j] < maxint)) {
int newdist = dist[u] + g.edge[u][j]; if (newdist < dist[j]) {
dist[j] = newdist; prev[j] = u; } } } } }
return dist[vn];
（4）输出所求最短路径所经过的顶点模块
void ShowPath(mgraph g,int v0,int u,int *dist,int *prev) {
int j= 0; int y=u;
int count = 0; int *way ;
way=(int *)malloc(sizeof(int)*(g.N+1)); //回溯路径 while (y!= v0) { count++;
}
way[count] = prev[y];
y= prev[y]; }
//输出路径
for (j=count;j>=1;j--) { }
printf(\
（5）求解任意两点之间的最短路径，须经过指定1个顶点模块 void zhiding1(mgraph g,int v0,int vn,int vx) {
int s1,s2,distance;
int *dist;//最短路径代价
int *prev;//前一跳节点空间 dist = (int *)malloc(sizeof(int)*g.N);
prev = (int *)malloc(sizeof(int)*g.N); printf(\输出路径是:\ s1=lujing(g,v0,vx,dist,prev); //计算v0到vx的最短路径
ShowPath(g,v0,vx,dist,prev);
s2=lujing(g,vx,vn,dist,prev); //计算vx到vn的最短路径 ShowPath(g,vx,vn,dist,prev); printf(\printf(\
distance=s1+s2; //合起来便是v0到vn的最短路径
终点为%d
的经过指定点%d
的最短路径
printf(\起始点为%d为:%d\
}
（6）求解任意两点之间的最短路径，须经过指定2个顶点模块 void zhiding2(mgraph g,int v0,int vn,int vx1,int vx2) {
int s11,s12,s13,s21,s22,s23,distance1,distance2,distance;
int *dist;//最短路径代价 int *prev;//前一跳节点空间
dist = (int *)malloc(sizeof(int)*g.N); prev = (int *)malloc(sizeof(int)*g.N);
printf(\输出路径是:\
s11=lujing(g,v0,vx1,dist,prev); s12=lujing(g,vx1,vx2,dist,prev);
s13=lujing(g,vx2,vn,dist,prev);
distance1=s11+s12+s13; //计算从v0经vx1经vx2到vn的最短路径 s21=lujing(g,v0,vx2,dist,prev); s22=lujing(g,vx2,vx1,dist,prev); s23=lujing(g,vx1,vn,dist,prev);
distance2=s21+s22+s23; //计算从v0经vx2经vx1到vn的最短路径 if(distance1 ShowPath(g,vx2,vn,dist,prev); printf(\printf(\ } else { distance=distance2; s21=lujing(g,v0,vx2,dist,prev); ShowPath(g,v0,vx2,dist,prev); s22=lujing(g,vx2,vx1,dist,prev); ShowPath(g,vx2,vx1,dist,prev); s23=lujing(g,vx1,vn,dist,prev); } ShowPath(g,vx1,vn,dist,prev); printf(\printf(\ printf(\起始点为%d终点为%d的经过指定点一%d以及指定点二%d的最短路径为:%d\} 3. 函数调用关系图： 4．完整的程序：(见源文件). 四 使用说明、测试分析及结果 Void hamidun() void zhiding1() void zhiding2() int main() int lujing() void ShowPath() 1．程序使用说明 （1）本程序的运行环境为VC6.0。 （2）进入演示程序后即显示提示信息： <1>请输入顶点数和边数(输入格式为:顶点数,边数):11,17 <2> 请输入顶点信息(输入格式为:顶点号):0 1 2 3 4 5 6 7 8 9 10 <3> 请输入每条边对应的两个顶点号及其权值(输入格式为:顶点,顶点,权值:): 0,6,5 0,7,4 0,4,3 1,4,1 1,6,8 1,3,2 2,4,6 2,3,3 2,10,7 3,5,8 5,10,3 5,9,8 6,7,1 7,8,4 7,9,6 8,9,2 9,10,6 2.测试结果： 请选择操作: <1>如果选择输入为1，结果为： 最短哈密尔顿回路为：0->6->7->8->9->5->10->2->3->1->4->0 权值为：5+1+4+2+8+3+7+3+2+1+3=39 <2>如果选择输入为2，结果为： 请输入指定起始点：0 请输入指定终点：6 请输入路径经过指定的顶点：10 输出路径是：0->4->2->10->9->7->6 起始点为0终点为6的经过指定点10的最短路径为：29 <3>如果选择输入为3，结果为: 请输入指定起始点：4 请输入指定终点：1 请输入路径经过指定的顶点一：8 请输入路径经过指定的顶点二：3 输出路径是：4->1->3->1->6->7->8->7->6->1 起始点为4终点为1的经过指定点一8以及指定点二3的最短路径为：31 <4>如果选择输入为0，结果为: 结束. 3．运行界面
相关推荐：
loading