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

}

}

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的最短路径