数据结构课程设计实验报告

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; } }