请问这个Floyd算法写最短路径出了什么问题？

Question

我用Floyd算法写最短路径，用的数据这个图，但是得出来的path[0] [7]是5不是4，为什么呢？

D中0到9的路径权值没有出错，但是path[0] [7]就出错了

代码：

#include<stdlib.h>
#include<stdio.h>
#include<string.h>

#define MaxVertexNum 100   //最大有100个顶点
#define INFINITY 65535      //定义无穷大
typedef int Vertex;
typedef int WeightType;
typedef int DataType;


// 顶点
struct Gnode{
    int Nv;     //顶点数
    int Ne;     //边数
    WeightType G[MaxVertexNum][MaxVertexNum];   //邻接矩阵
    DataType Data[MaxVertexNum];    //顶点数据
};
typedef struct Gnode *MGraph;

// 边
struct Enode{
    Vertex V1, V2;      //又向边<V1,V2>
    WeightType Weight;      //权重
};
typedef struct Enode *Edge;

//  初始化有VertexNum个顶点的无边的图
MGraph CreatGraph( int VertexNum )
{
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct Gnode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0; //无边
    for( V = 0; V < Graph->Nv; V++ ){
        for( W = 0; W < Graph->Nv; W++ ){
            Graph->G[V][W] = INFINITY;
        }
    }

    return Graph;
}

//插入边
void InsertEdge( MGraph Graph, Edge E )
{
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}

//构建图
MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv;

    //初始化图
    printf("输入顶点数：");
    scanf("%d", &Nv);
    Graph = CreatGraph( Nv );
    

    //输入边
    printf("\n输入边数：");
    scanf("%d", &(Graph->Ne));
    if( Graph->Ne != 0 ){
        E = (Edge)malloc(sizeof(struct Enode));
        for( int i = 0; i < Graph->Ne; i++ ){
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge( Graph, E );
        }
    }

    //顶点数据
    printf("\n输入顶点数据：\n");
    for( V = 0; V < Graph->Nv; V++ ){
        scanf(" %d",&Graph->Data[V]);
    }

    return Graph;
}

void Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    //初始化path[]和Distance
    for( int i = 0; i < Graph->Nv; i++ ){
        for( int j = 0; j < Graph->Nv; j++ ){
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }
    }

    //Floyd算法
    for( int k = 0; k < Graph->Nv; k++ ){
        for( int i = 0; i < Graph->Nv; i++ ){
            for( int j = 0; j < Graph->Nv; j++ ){
                if( D[i][k] + D[k][j] < D[i][j] ){
                    D[i][j] = D[i][k] + D[k][j];                
                    path[i][j] = k;
                }
            } 
        }
    }

    //return true;
}


int main()
{
    MGraph Graph;
    Graph = BuildGraph();

    printf("\n这是邻接矩阵：\n");
    for( int i = 0; i < Graph->Nv; i++ ){
        for( int j = 0; j < Graph->Nv; j++ ){
            printf("%-8d", Graph->G[i][j]);
        }
        printf("\n");
    }

    //最短路径
    int D[MaxVertexNum][MaxVertexNum];
    int path[MaxVertexNum][MaxVertexNum];
    Floyd( Graph, D, path );

    Vertex V1, V2;
    printf("起点：");
    scanf("%d", &V1);
    printf("终点：");
    scanf("%d", &V2);

    
    int v1, v2; 
    for( v1 = 0; v1 < Graph->Nv; v1++){
        if( V1 == v1 )
            break;
    }
    for( v2 = 0; v2 < Graph->Nv; v2++){
        if( V2 == v2 )
            break;
    }

    while( path[v1][v2] != -1 ){
        printf("%d<-", Graph->Data[path[v1][v2]] );
        v2 = path[v1][v2];
    }

    
    return 0;
}

测试数据：

10
17
0 1 2
0 3 5
1 2 5
1 3 2
2 4 8
2 5 4
3 5 4
3 6 2
4 5 2
4 7 5
5 6 3
5 7 9
5 8 6
6 8 7
7 8 3
7 9 4
8 9 8
0
1
2
3
4
5
6
7
8
9

Answer 1

算法没有问题，path定义有问题。

从算法分析，path[i][j]应该表示为必经点，但不一定是最后一个点。