长沙地铁线路查询并加上查询最短路径的C语言代码

以下是使用Dijkstra算法实现长沙地铁线路最短路径查询的C语言代码：

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

#define INF 1e9 // 定义无穷大

// 定义地铁站结构体
typedef struct {
    char name[20]; // 站名
    int id; // 站点编号
    int line; // 所属线路
} Station;

// 定义邻接表节点结构体
typedef struct {
    int to; // 指向的站点编号
    int weight; // 边权值，即两站之间的距离
    int next; // 下一个邻接表节点的编号
} Edge;

// 定义邻接表结构体
typedef struct {
    int head[100]; // 邻接表头指针数组
    Edge edge[1000]; // 邻接表节点数组
    int cnt; // 邻接表节点计数器
} AdjacencyList;

// 定义全局变量
Station station[100]; // 站点数组
AdjacencyList graph; // 地铁线路邻接表
int stationCnt = 0; // 站点计数器

// 初始化邻接表
void initGraph() {
    memset(graph.head, -1, sizeof(graph.head)); // 初始化邻接表头指针数组
    graph.cnt = 0; // 初始化邻接表节点计数器
}

// 添加站点
void addStation(char *name, int line) {
    strcpy(station[stationCnt].name, name);
    station[stationCnt].id = stationCnt;
    station[stationCnt].line = line;
    stationCnt++;
}

// 添加边
void addEdge(int u, int v, int w) {
    graph.edge[graph.cnt].to = v;
    graph.edge[graph.cnt].weight = w;
    graph.edge[graph.cnt].next = graph.head[u];
    graph.head[u] = graph.cnt++;
}

// 查询站点编号
int findStation(char *name) {
    for (int i = 0; i < stationCnt; i++) {
        if (strcmp(station[i].name, name) == 0) {
            return i;
        }
    }
    return -1; // 没有找到该站点
}

// 查询最短路径
void dijkstra(int start, int end) {
    int dis[100]; // 存储起点到各站点的最短距离
    int vis[100]; // 标记站点是否已访问
    int pre[100]; // 记录每个站点的前驱站点
    memset(dis, INF, sizeof(dis)); // 初始化距离数组
    memset(vis, 0, sizeof(vis)); // 初始化访问标记数组
    memset(pre, -1, sizeof(pre)); // 初始化前驱数组
    dis[start] = 0; // 起点到起点的最短距离为0

    // Dijkstra算法
    for (int i = 0; i < stationCnt; i++) {
        int minDis = INF, u = -1;
        for (int j = 0; j < stationCnt; j++) {
            if (!vis[j] && dis[j] < minDis) {
                minDis = dis[j];
                u = j;
            }
        }
        if (u == -1) break;
        vis[u] = 1;
        for (int j = graph.head[u]; j != -1; j = graph.edge[j].next) {
            int v = graph.edge[j].to;
            int w = graph.edge[j].weight;
            if (!vis[v] && dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pre[v] = u;
            }
        }
    }

    // 输出最短路径
    printf("从 %s 到 %s 的最短路径为：\n", station[start].name, station[end].name);
    printf("%s", station[start].name);
    int path[100], cnt = 0;
    for (int i = end; i != -1; i = pre[i]) {
        path[cnt++] = i;
    }
    for (int i = cnt - 2; i >= 0; i--) {
        printf(" -> %s", station[path[i]].name);
    }
    printf("\n最短距离为：%d\n", dis[end]);
}

int main() {
    // 添加地铁站点
    addStation("岳麓山", 1);
    addStation("梅溪湖", 1);
    addStation("南瓜", 1);
    addStation("高云", 1);
    addStation("岳麓大道", 1);
    addStation("轨道交通大厦", 1);
    addStation("西湖公园", 2);
    addStation("芙蓉广场", 2);
    addStation("五一广场", 2);
    addStation("万家丽", 2);
    addStation("长沙火车站", 2);
    addStation("开福寺", 2);

    // 添加地铁线路
    initGraph();
    addEdge(0, 1, 3);
    addEdge(1, 2, 2);
    addEdge(2, 3, 2);
    addEdge(3, 4, 2);
    addEdge(4, 5, 2);
    addEdge(5, 6, 2);
    addEdge(6, 7, 2);
    addEdge(7, 8, 2);
    addEdge(8, 9, 2);
    addEdge(9, 10, 2);
    addEdge(10, 11, 2);
    addEdge(11, 7, 1);
    addEdge(8, 5, 1);
    addEdge(4, 9, 1);

    // 查询最短路径
    int start = findStation("岳麓山");
    int end = findStation("长沙火车站");
    dijkstra(start, end);

    return 0;
}

其中，`addStation`函数用于添加地铁站点，`addEdge`函数用于添加地铁线路，`findStation`函数用于查询站点编号，`dijkstra`函数用于查询最短路径。在本示例中，我们以长沙地铁1号线和2号线为例添加地铁站点和地铁线路，并查询了岳麓山站到长沙火车站的最短路径。