dijkstra求带权无向图最短路径问题

#include<stdio.h>
#include<string.h>
#define N 100 //图最大顶点数
#define INF 0x3f3f3f3f//无穷大距离
typedef struct{
    int vex[N][N];
    int Vnum,Enum;
}Graph;
 
void CreateGraph(Graph *G){
    memset(G->vex,INF,sizeof(G->vex));
    printf("请输入图的顶点数和边数:");
    scanf("%d%d",&G->Vnum,&G->Enum);
    printf("请按行输入边对应权值:\n");
    for(int i=0;i<G->Enum;i++){
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        scanf("%d",&G->vex[v1][v2]);
    }
    printf("\n");
}//创建图
 
void Dijkstra(Graph *G){
    int book[G->Vnum]={0};//用于判断点是否已找到最短路径
    int dist[G->Vnum],start,end;//dist用于记录当前路径长度
    int path[G->Vnum];//用于记录最短路径
    printf("请输入起点和终点:\n");
    scanf("%d%d",&start,&end);
    memset(dist,INF,sizeof(dist));//初始化dist数组
    dist[start]=0;
    while(1){
        int MIN=INF,u=-1;
        for(int i=0;i<G->Vnum;i++)
            if(dist[i]<MIN&&book[i]==0){
                MIN=dist[i];
                u=i;
            }
        if(u==-1)
            break;//说明图不连通
        book[u]=1;
        for(int i=0;i<G->Vnum;i++)
            if(dist[u]+G->vex[u][i]<dist[i]){
                dist[i]=dist[u]+G->vex[u][i];
                path[i]=u;
            }//更新最短路径以及最短距离
    }
    int temp[N],t=0,x=end;
    while(x!=start){
        temp[t++]=x;
        x=path[x];
    }//逆序记录路径
    temp[t]=start;
    printf("最短路径:");
    for(int i=t;i>0;i--)
        printf("%d->",temp[i]);
    printf("%d\n",end);
    printf("最短路径长度为:%d",dist[end]);
 
}//dijkstra算法遍历图求最短距离
 
int main(){
    Graph G;
    CreateGraph(&G);
    Dijkstra(&G);
}

图1

图2

参考资料:
【全网第二清晰】手写迪杰斯特拉-Dijkstra（考试用）_哔哩哔哩_bilibili
【c语言】Dijkstra算法，邻接矩阵实现_dijkstra 邻接矩阵c语言实现-CSDN博客