void Floyd(MGraph *G)
//用Floyd算法求图中各对顶点v和w之间的最短路径P[v][w]及其
//带权长度D[v][w]。若P[v][w][u]为1，则u是从v到w当前求得最短
//路径上的顶点。
{
int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
for(v=0;v<G->vexnum;v++) //各对结点之间初始已知路径及距离
for(w=0;w<G->vexnum;w++)
{
D[v][w]=G->arcs[v][w].adj;
for(u=0;u<G->vexnum;u++)
p[v][w][u]=0;
if(D[v][w]<INFINITY)
{
p[v][w][v]=1;p[v][w][w]=1;
}
}
for(u=0;u<G->vexnum;u++)
for(v=0;v<G->vexnum;v++)
for(w=0;w<G->vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]) //从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w]; //修改权值
for(i=0;i<G->vexnum;i++)
p[v][w][i]=p[v][u][i]||p[u][w][i];
}
while(flag)
{
printf("请输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
if(k<0||k>G->vexnum||j<0||j>G->vexnum)
{
printf("景点编号不存在!请重新输入出发点和目的地的编号:");
scanf("%d%d",&k,&j);
}
if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)
flag=0;
}
printf("%s",G->vexs[k].name);
for(u=0;u<G->vexnum;u++)
问题出在这里
if(p[k][j][u]&&k!=u&&j!=u)
printf("-->%s",G->vexs[u].name);
printf("-->%s",G->vexs[j].name);
printf(" 总路线长%dm\n",D[k][j]);
}//Floyd end
我已经知道问题了，就是我每当输出两点之间的最短路径时候，输出的地点信息不按顺序，距离是对的，应该是缺少一个地点输出的排序语句，但是我不知道该怎么编写排序语句。求指导。比如我输入 理工楼到音乐楼 正确的是 理工楼 传信桥 音乐楼 距离200m。但是，它输出的顺序是理工楼 音乐楼 传信桥 200m
因为你只记录了u是否是k到j的最短路径上的点。。。并没有记录他们的相对顺序啊
试一下这个代码可以不
void PrintShortestPath(const MGraph* G, int(&p)[10][10][10], int st, int ed) {
int i;
for (i = 0; i < G->vexnum; i++) {
if (i != st && i != ed && p[st][ed][i]) {
PrintShortestPath(G, p, st, i);
PrintShortestPath(G, p, i, ed);
return;
}
}
printf("-->%s", G->vexs[ed].name);
}
void Floyd(MGraph *G)
//用Floyd算法求图中各对顶点v和w之间的最短路径P[v][w]及其
//带权长度D[v][w]。若P[v][w][u]为1，则u是从v到w当前求得最短
//路径上的顶点。
{
int v, u, i, w, k, j, flag = 1, p[10][10][10], D[10][10];
for (v = 0; v < G->vexnum; v++) //各对结点之间初始已知路径及距离
for (w = 0; w < G->vexnum; w++)
{
D[v][w] = G->arcs[v][w].adj;
for (u = 0; u < G->vexnum; u++)
p[v][w][u] = 0;
if (D[v][w] < INFINITY)
{
p[v][w][v] = 1; p[v][w][w] = 1;
}
}
for (u = 0; u < G->vexnum; u++)
for (v = 0; v < G->vexnum; v++)
for (w = 0; w < G->vexnum; w++)
if (D[v][u] + D[u][w] < D[v][w]) //从v经u到w的一条路径更短
{
D[v][w] = D[v][u] + D[u][w]; //修改权值
for (i = 0; i < G->vexnum; i++)
p[v][w][i] = p[v][u][i] || p[u][w][i];
}
while (flag)
{
printf("请输入出发点和目的地的编号:");
scanf("%d%d", &k, &j);
if (k<0 || k>G->vexnum || j<0 || j>G->vexnum)
{
printf("景点编号不存在!请重新输入出发点和目的地的编号:");
scanf("%d%d", &k, &j);
}
if (k >= 0 && k < G->vexnum&&j >= 0 && j < G->vexnum)
flag = 0;
}
printf("%s", G->vexs[k].name);
PrintShortestPath(G, p, k, j);
printf(" 总路线长%dm\n", D[k][j]);
}//Floyd end
