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

地铁线路最短路径可以使用 Dijkstra 算法来实现。以下是 C 语言实现的示例代码：

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

#define MAX_STATIONS 100 // 最大站点数

int graph[MAX_STATIONS][MAX_STATIONS]; // 地铁线路图
int dist[MAX_STATIONS]; // 记录起点到每个站点的最短距离
bool visited[MAX_STATIONS]; // 记录每个站点是否已访问

// 初始化图
void initGraph(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0; // 初始距离为0
        }
    }
}

// 添加地铁站点之间的距离
void addEdge(int u, int v, int w) {
    graph[u][v] = graph[v][u] = w;
}

// 寻找起点到最短距离最小的站点
int findMinDistIndex(int n) {
    int minDist = INT_MAX;
    int minIndex = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < minDist) {
            minDist = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

// 计算起点到其他站点的最短距离
void dijkstra(int n, int start) {
    // 初始化距离
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    dist[start] = 0; // 起点到自己的距离为0

    for (int i = 0; i < n - 1; i++) {
        int u = findMinDistIndex(n); // 找到距离起点最近的站点
        visited[u] = true;

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

int main() {
    int n, m; // n 表示站点数，m 表示路线数
    scanf("%d %d", &n, &m);

    initGraph(n);

    // 输入路线信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);
    }

    int start; // 起点站
    scanf("%d", &start);

    dijkstra(n, start);

    // 输出起点到每个站点的最短距离
    for (int i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");

    return 0;
}

在以上代码中，`graph` 数组用于存储地铁线路图，`dist` 数组用于记录起点到每个站点的最短距离，`visited` 数组用于记录每个站点是否已访问。`initGraph` 函数用于初始化图，`addEdge` 函数用于添加地铁站点之间的距离。`findMinDistIndex` 函数用于寻找起点到最短距离最小的站点。`dijkstra` 函数用于计算起点到其他站点的最短距离。在 `main` 函数中，首先输入站点数和路线数，然后输入路线信息，最后输入起点站。最后输出起点到每个站点的最短距离。