发布时间 : 星期六 文章数据结构课程设计实验报告更新完毕开始阅读
}
}
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(\printf(\printf(\ 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; } } 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]; } 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(\ } } //求解任意两个顶点之间的经过指定一顶点的最短路径 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的最短路径 printf(\起始点为%d终点为%d的经过指定点%d 最短路径 的为:%d\ } //求解任意两个顶点之间的经过指定两顶点的最短路径 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 distance=distance1; s11=lujing(g,v0,vx1,dist,prev); ShowPath(g,v0,vx1,dist,prev); s12=lujing(g,vx1,vx2,dist,prev); ShowPath(g,vx1,vx2,dist,prev); s13=lujing(g,vx2,vn,dist,prev); 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的最短路径