狄克斯特拉算法c语言邻接矩阵

以下是狄克斯特拉算法的C语言代码，使用邻接矩阵表示图：

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

#define MAX_VERTICES 100
#define INF INT_MAX

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示图
int dist[MAX_VERTICES]; // 存储最短路径
int visited[MAX_VERTICES]; // 记录节点是否已经被访问过

int dijkstra(int start, int end, int n) {
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[start] = 0;

    for (int i = 0; i < n; i++) {
        // 找到未访问节点中距离起点最近的节点
        int min_dist = INF;
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        if (u == -1) break;

        visited[u] = 1;

        // 更新与该节点相邻的节点的最短路径
        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    return dist[end];
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) graph[i][j] = 0;
            else graph[i][j] = INF;
        }
    }

    // 读入边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        graph[u][v] = w;
        graph[v][u] = w;
    }

    int start, end;
    scanf("%d %d", &start, &end);

    int shortest_path = dijkstra(start, end, n);
    printf("%d\n", shortest_path);

    return 0;
}

在这个代码中，我们使用了邻接矩阵来表示图，其中 `graph[i][j]` 表示节点 `i` 和节点 `j` 之间的边权值。我们使用了 `dist` 数组来存储起点到各个节点的最短路径长度，使用 `visited` 数组来记录节点是否已经被访问过。算法的具体实现方法与伪代码相同，这里不再赘述。