用Floyd算法求一个图中的两点间的最短路径
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define INFINITY INT_MAX
#define MAXSIZE 100
#define MAXVEX 6
#define FALSE 0
#define TRUE 1
typedef char VexType;
typedef float AdjType;
typedef struct
{ int vexnum; /* 图的顶点个数 */
VexType vexs[MAXVEX]; /* 顶点信息 */
AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */
}MGraph;
MGraph G;
AdjType D[MAXVEX][MAXVEX]; /*D(v)为v0到v的路径长度*/
int p[MAXVEX][MAXVEX][MAXVEX]; /*p(v)记录v0到v的最短路径，若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点*/
int final[MAXVEX]; /*final[v]为TRUE当且仅当v∈s,即已求得从v0到v的最短路径*/
void ShortestPath_FLOYD(MGraph G,int p[MAXVEX][MAXVEX][MAXVEX],AdjType D[MAXVEX][MAXVEX])
{//Floyd算法
int v,w,u,i;
for(v=0;v<G.vexnum;++v)
for(w=0;w<G.vexnum;++w)
{
D[v][w]=G.arcs[v][w];
for(u=0;u<G.vexnum;++u)
p[v][w][u]=FALSE;
if(D[v][w]<INFINITY)
{
p[v][w][u]=TRUE;
p[v][w][w]=TRUE;
}
}
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])
{
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];
}
}
main()
{ int i,j,a,b,k;
int x[10];
G.vexnum=6;
scanf("%d%d",&a,&b);
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY; /*G数组初始化最大值*/
G.arcs[0][1]=50; G.arcs[0][2]=10; G.arcs[1][2]=15; G.arcs[1][4]=5;
G.arcs[2][0]=20; G.arcs[2][3]=15; G.arcs[3][1]=20; G.arcs[3][4]=35;
G.arcs[4][3]=30; G.arcs[5][3]=3; G.arcs[0][4]=45; G.arcs[2][5]=11;
ShortestPath_FLOYD(G,p,D);
for(i=0;i<G.vexnum;i++) /*以邻接矩阵形式输出图*/
{ for(j=0;j<G.vexnum;j++)
printf("%11.0f ",G.arcs[i][j]);
printf("\n");
}
printf("\n");
printf("%.0f ",D[a][b]);
printf("\n");
}
以上程序是用Floyd算法求一个图中的两点间的最短路径
长度已经求出来了，但我希望能输出具体的路径，就是输出
最短路径的每一个结点，请哪位高手在我程序的基础上修改一下，
实现我的目的，谢谢！！
[解决办法]
Floyd算法是一个经典的动态规划。一个矩阵乘了n次，每乘一次都在作路径寻找和替换，你仔细看看这个算法的全过程，找几个规模小的图手动运行一下Floyd算法。要记录这个路径其实挺简单的，模仿dijstra算法就可以。代码自己写吧，这样理解更深一些。
