floyd算法导游问题

floyd算法导游问题

因为你只记录了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
", D[k][j]);

}//Floyd end