用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算法就可以。代码自己写吧，这样理解更深一些。