婵犵數濮烽。顔炬閺囥垹纾婚柟杈剧畱绾惧綊鏌″搴″箹缁炬儳娼￠弻鐔烘崉閸濆嫷妫￠梺鎼炲労閸撴岸寮查幖浣圭叆闁绘洖鍊圭€氾拷}
}
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的最短路径