[数据结构与算法]迪杰斯特拉算法（c语言）

#include <stdio.h>
#define MAX 100
#define INFINITY 10000

typedef struct graph{
    char vexs[MAX];       // 顶点集合
    int vexnum;           // 顶点数
    int arcnum;           // 边数
    int arc[MAX][MAX]; // 邻接矩阵
}MGraph,*PGraph;

void create_graph(PGraph G){
    int i,j,k,w;
    printf("请输入顶点数和边数：");
    scanf("%d%d",&G->vexnum,&G->arcnum);
    getchar();
    for(i=0;i<G->vexnum;i++){
        printf("请输入%d个顶点的信息\n",i+1);
        scanf("%c",&G->vexs[i]);
        getchar();
    }
    //邻接矩阵的初始化,对角线为0，其他地方为infinity，ps：此处我把节点到自己本身的值也设置为infinity了
    for(i=0;i<G->vexnum;i++){
        for (j=0; j<G->vexnum; j++) {
            if(i==j)
                G->arc[i][j] = INFINITY;
            else
                G->arc[i][j] = INFINITY;
        }
    }
    //对邻接矩阵进行赋值
    for(k=0;k<G->arcnum;k++){
        printf("输入边(vi,vj)的下标i,j以及权值w:");
        scanf("%d%d%d",&i,&j,&w);
        G->arc[i][j] = w;
        G->arc[j][i] = w;
    }
}

//可以检验图建立的有没有问题
void print_graph(PGraph G){
    int i,j;
    for(i=0;i<G->vexnum;i++){
        for(j=0;j<G->vexnum;j++){
            printf("%-10d",G->arc[i][j]);
        }
        printf("\n");
    }
}

void Dijkstra(PGraph G){
    //目前这个程序中规定源点为0
    int k=0;
    int dis[G->vexnum];
    int used[G->vexnum];//下标从0开始,该数组用来标明是否归并
    for(int i=0;i<G->vexnum;i++){
        used[i] = 0;
    }
    for(int i=1;i<G->vexnum;i++){
        dis[i] = G->arc[0][i];//dis[i]下标i对应的是vi
    }
    used[0] = 1;
    for(int i=1;i<G->vexnum;i++){
        int tmin;
        tmin = 1000;
        for(int j=1;j<G->vexnum;j++){
            if(!used[j]&&tmin>dis[j]){
                tmin = dis[j];
                k = j;
            }//该循环找到源点到未归并顶点距离最小的点
        }
        used[k] = 1;
        for(int j=1;j<G->vexnum;j++){
            if(dis[k]+G->arc[k][j]<dis[j]&&!used[j]){
                dis[j] = dis[k]+G->arc[k][j];
            }
        }
        printf("v0到v%d的最短距离为：%d\n",k,dis[k]);
    }
}

int main(){
    MGraph G;
    create_graph(&G);
    print_graph(&G);
    Dijkstra(&G);
}