C语言实现Dijkstra算法求最短路径

使用Dijkstra算法可以实现给定一个源点，求其到其余节点的最短路径。下面是C语言实现的代码：

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

#define MAX_VERTEX_NUM 100

// 无穷大
#define INFINITY INT_MAX

// 图的邻接矩阵存储结构
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存储顶点信息
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权值
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

// Dijkstra算法求最短路径
void Dijkstra(Graph g, int start, int* path, int* dist) {
    int visited[MAX_VERTEX_NUM] = { 0 }; // 记录结点是否被访问过
    visited[start] = 1; // 标记起点已访问
    for (int i = 0; i < g.vertex_num; i++) {
        dist[i] = g.edge[start][i]; // 初始化起点到各结点的距离
        path[i] = (dist[i] == INFINITY) ? -1 : start; // 初始化路径
    }
    for (int i = 0; i < g.vertex_num - 1; i++) {
        int min_dist = INFINITY, min_index = -1; // 记录最小距离和对应的结点
        for (int j = 0; j < g.vertex_num; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }
        if (min_index == -1) break; // 找不到未访问结点
        visited[min_index] = 1; // 标记最小距离对应的结点已访问
        for (int j = 0; j < g.vertex_num; j++) {
            if (!visited[j] && g.edge[min_index][j] != INFINITY && dist[min_index] + g.edge[min_index][j] < dist[j]) {
                // 更新起点到未访问结点的距离和路径
                dist[j] = dist[min_index] + g.edge[min_index][j];
                path[j] = min_index;
            }
        }
    }
}

int main() {
    Graph g = {
        {0, 1, 2, 3, 4},
        {
            {0, 1, INFINITY, 2, INFINITY},
            {INFINITY, 0, 4, INFINITY, INFINITY},
            {INFINITY, INFINITY, 0, INFINITY, 3},
            {INFINITY, INFINITY, 1, 0, INFINITY},
            {INFINITY, INFINITY, INFINITY, INFINITY, 0}
        },
        5,
        7
    };
    int start = 0;
    int path[MAX_VERTEX_NUM]; // 记录到各结点的路径
    int dist[MAX_VERTEX_NUM]; // 记录起点到各结点的距离
    Dijkstra(g, start, path, dist);
    printf('起点为%d时各结点的最短路径和距离为：\n', start);
    for (int i = 0; i < g.vertex_num; i++) {
        if (i == start) continue;
        printf('%d -> %d : ', start, i);
        if (dist[i] == INFINITY) {
            printf('无法到达\n');
        }
        else {
            printf('%d', i);
            for (int j = path[i]; j != start; j = path[j]) {
                printf(' <- %d', j);
            }
            printf(' <- %d，距离为%d\n', start, dist[i]);
        }
    }
    return 0;
}

上述代码中，我们使用了邻接矩阵来存储图，并在Dijkstra算法中使用了一个visited数组来记录结点是否被访问过，一个path数组来记录到各结点的路径，一个dist数组来记录起点到各结点的距离，最终输出起点为start时各结点的最短路径和距离。