地铁线路最短路径实现 C语言

实现地铁线路最短路径可以使用 Dijkstra 算法，其基本思想是从起点开始，每次选择当前最短路径的节点进行扩展，直到到达终点或者所有可达节点都已经被扩展。在这个过程中，需要维护一个距离数组，记录每个节点到起点的最短距离。

以下是使用 C 语言实现该算法的示例代码：

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

#define MAX_N 1000
#define INF INT_MAX

int n; // 点数
int m[MAX_N][MAX_N]; // 邻接矩阵表示边权
int dist[MAX_N]; // 距离数组，记录每个点到起点的最短距离
int visited[MAX_N]; // 标记数组，记录每个点是否已经被扩展

void dijkstra(int start) {
    // 初始化距离数组和标记数组
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[start] = 0;

    // 扩展节点
    for (int i = 0; i < n; i++) {
        int u = -1;
        int min_dist = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) break;
        visited[u] = 1;

        // 更新距离数组
        for (int v = 0; v < n; v++) {
            if (!visited[v] && m[u][v] != INF && dist[u] + m[u][v] < dist[v]) {
                dist[v] = dist[u] + m[u][v];
            }
        }
    }
}

int main() {
    int start, end;
    scanf("%d %d %d", &n, &start, &end);
    start--; end--;

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

    // 读入边权
    int u, v, w;
    while (scanf("%d %d %d", &u, &v, &w) != EOF) {
        u--; v--;
        m[u][v] = m[v][u] = w;
    }

    // 使用 Dijkstra 算法计算最短路径
    dijkstra(start);

    // 输出结果
    if (dist[end] == INF) {
        printf("No path\n");
    } else {
        printf("%d\n", dist[end]);
    }

    return 0;
}

在输入时，第一行为点数、起点和终点，接下来的每一行为一条边，格式为“起点 终点 边权”，以 EOF 结束。输出为最短路径的长度，如果不存在路径则输出“No path”。