dijkstra算法c语言 代码

Dijkstra算法是一种经典的单源最短路径算法，其目的是找出从一个源点到其他所有点的最短路径。下面是Dijkstra算法的C语言实现代码：

#include <stdio.h>
#define INF 9999  // 定义无穷大

int main()
{
    int n, i, j, min, start;  // n表示顶点数，start表示起点编号
    int dist[100], vis[100], graph[100][100];  // dist数组记录起点到各个顶点的最短距离，vis数组记录该顶点是否已被访问，graph存储图的邻接矩阵
    printf("请输入顶点数：");
    scanf("%d", &n);
    printf("请输入图的邻接矩阵：\n");
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    printf("请输入起点编号：");
    scanf("%d", &start);

    // 初始化dist和vis数组
    for(i = 0; i < n; i++) {
        dist[i] = graph[start][i];
        vis[i] = 0;
    }
    vis[start] = 1;

    // Dijkstra算法核心代码
    for(i = 0; i < n-1; i++) {
        min = INF;
        for(j = 0; j < n; j++) {
            if(!vis[j] && dist[j] < min) {
                min = dist[j];
                start = j;
            }
        }
        vis[start] = 1;
        for(j = 0; j < n; j++) {
            if(!vis[j] && dist[start]+graph[start][j] < dist[j]) {
                dist[j] = dist[start]+graph[start][j];
            }
        }
    }

    // 输出起点到各个顶点的最短距离
    printf("起点%d到各个顶点的最短距离为：\n", start);
    for(i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
    return 0;
}