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

Z时代
2024-01-10
分类：IT

我用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");
    }
    //路径" title="最短路径">最短路径
    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;}