地铁线路最短路径实现c

实现地铁线路最短路径的算法常用的是 Dijkstra 算法，以下是 C 语言实现：

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

#define MAX_STATION 1000 // 地铁站点数量的最大值
#define INF INT_MAX // 定义无穷大值

int n; // 地铁站点数量
int map[MAX_STATION][MAX_STATION]; // 地铁站点间的距离矩阵
int dist[MAX_STATION]; // 存储源点到各点的最短距离
int visited[MAX_STATION]; // 存储各点的访问状态

// 初始化地铁图
void init_map() {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            map[i][j] = INF;
        }
    }
}

// 计算源点到各点的最短距离
void dijkstra(int src) {
    int i, j, k, min_dist;
    for (i = 0; i < n; i++) {
        visited[i] = 0;
        dist[i] = map[src][i];
    }
    visited[src] = 1;
    dist[src] = 0;
    for (i = 0; i < n - 1; i++) {
        min_dist = INF;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                k = j;
                min_dist = dist[j];
            }
        }
        visited[k] = 1;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[k] + map[k][j] < dist[j]) {
                dist[j] = dist[k] + map[k][j];
            }
        }
    }
}

int main() {
    int i, j, m, a, b, d, s, t;
    scanf("%d%d", &n, &m);
    init_map();
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &d);
        map[a][b] = d;
        map[b][a] = d;
    }
    scanf("%d%d", &s, &t);
    dijkstra(s);
    printf("%d\n", dist[t]);
    return 0;
}

这段代码实现了 Dijkstra 算法，输入格式如下：

n m
a1 b1 d1
a2 b2 d2
...
am bm dm
s t

其中，n 表示地铁站点数量，m 表示地铁线路数量，a 和 b 表示地铁站点的编号，d 表示两个站点之间的距离。s 和 t 分别表示起点和终点的编号。

输出为源点到终点的最短距离。