发布时间 : 星期三 文章数据结构课程设计实验报告更新完毕开始阅读
printf(\求解任意两个顶点之间的经过指定两顶点的最短路径.\\n\
printf(\结束操作.\\n\
printf(\ printf(\请选择操作:\ scanf(\ switch(m) {
case 1: printf(\最短哈密尔顿回路为:\ hamidun(g);
break;
case 2:
printf(\
经
过
指
定
径:****************\\n\
printf(\请输入指定起始点:\\n\ scanf(\
printf(\请输入指定终点:\\n\ scanf(\
printf(\请输入路径经过指定的顶点:\\n\ scanf(\ zhiding1(g,v0,vn,vx); printf(\ break;
case 3:
printf(\经
过
指
定
径:****************\\n\ printf(\请输入指定起始点:\\n\ scanf(\
printf(\请输入指定终点:\\n\
scanf(\
printf(\请输入路径经过指定的顶点一:\\n\ scanf(\
printf(\请输入路径经过指定的顶点二:\\n\ scanf(\
zhiding2(g,v0,vn,vx1,vx2);
printf(\ break; case 0:
exit(0);
default: printf(\输出出错！\\n\
} }
getchar();
一
点
最
两
点
最
短
路
短
路
getchar();
return 0; }
（2）求解最短哈密尔顿回路模块 void hamidun(mgraph &g) { int i,j;
//记忆最短路径
Node aShortNode[M]; //记忆当前路径 Node aNode[M]; for(i=0;i } //最短回路长度 int length=MAX_LENGTH; //压入第一个节点 Node node; node.dot=0; node.level=0; top++; s[top]=node; int po=0; int len=0; while(top!=-1) { //记录路径节点 aNode[po]=s[top]; top--; bool isEnd=false; //一条回路是否结束 if(po>=1) { len=len+g.edge[aNode[po-1].dot][aNode[po].dot]; if(len>length po==g.N-1||g.edge[aNode[po-1].dot][aNode[po].dot]==999) isEnd=true; } if(isEnd) { //完整回路 if(po==g.N-1) || } { } //路径回溯 if(top!=-1) { } node=s[top]; for(i=po;i>=node.level;i--) { len=len-g.edge[aNode[i-1].dot][aNode[i].dot]; aNode[i].dot=-1; len=len+g.edge[0][aNode[g.N-1].dot]; if(len //更改当前最短路径 for(i=0;i aShortNode[i]=aNode[i]; len=len-g.edge[0][aNode[g.N-1].dot]; aNode[i].level=-1; } //更新当前层 po=node.level; else { po++; //下一层 //将下一层节点入栈 for(i=0;i //判断下一个压栈的节点在不在当前路径 bool isIn=false; for(j=0;j if(i==aNode[j].dot) { isIn=true; break; } } //不在当前路径 } } } } if(!isIn) { } node.dot=i; node.level=po; top++; s[top]=node; for(i=0;i printf(\ printf(\ printf(\ printf(\权值为:\ for(i=1;i printf(\ （3）求解指定两点之间的最短路径模块 int lujing(mgraph g,int v0,int vn,int dist[],int prev[]) { int i; int j; int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值 int *s ;//定义具有最短路径的节点子集s s = (int *)malloc(sizeof(int) *g.N); //初始化最小路径代价和前一跳节点值 for (i= 0; i dist[i] = g.edge[v0][i]; s[i] = 0; if (dist[i] == maxint) { prev[i] = 0; } else { prev[i] = v0; } }