1. 先把怎么走翻译成图论问题“人民广场怎么走”这种问题日常交给手机地图就够了。但我自己作为一个写代码的人更喜欢把它当成一个算法题来拆给定一张城市地铁网、一个起点站、一个终点站程序要自己算出该怎么坐、在哪换、换几次。回答这个问题的底层核心就是地铁换乘算法。这篇文章聊的不是某个商业App的完整方案而是一个用C语言就能实现的迷你换乘引擎。我会完整走一遍从图建模、数据结构选型、Dijkstra变体设计到代码实作的全过程同时把换乘次数换乘时间这类现实约束翻译成算法里的权重。文章最后会给出可以直接编译运行的完整C代码以及几组真实查询的运行结果。适合两类人看一类是刚学完数据结构、想看看最短路径算法怎么落地的新手另一类是想在项目里快速做一个轻量级出行路线模块、又不想引入重量级依赖的开发者。看完至少能自己扩展出带首末班时间、带站点实时客流等功能的换乘原型。1.1 站点是点、区间是边一张地铁网的图模型要把人民广场怎么走交给程序第一步就是把地铁网变成程序认识的东西。最自然的建模方式是把地铁网抽象成一张无向图。站点是顶点相邻两站之间的轨道区间是边。每条边至少携带三个信息两端站点、属于哪条线路、跑完这个区间要多久。换乘站呢就是一个同时被多条线路共用的顶点。打个比方把地铁图想成一张只能沿着轨道走的旅游地图你从大学城走去火车站唯一能走的路就是图上画出来的轨道区间走到交叉口换乘站时你可以从一条轨道换到另一条轨道前提是付出一点额外体力——在真实世界里就是下车、走路、等车。这个抽象的价值在于它把人民广场怎么走从一个日常问路问题变成了一个数学问题在带权无向图中找一条从起点站到终点站的代价最小路径。一旦完成这个翻译后面所有算法都有章可循。无向图的选择也有讲究。绝大多数地铁线路是双向运行的所以每添加一个区间都要同时建立两个方向的边。如果漏掉反方向算法就会跑出坐过站之后回不去这种反人类结果。环线也不特殊它只是两条边首尾相接形成闭合建模方式没有任何额外负担。1.2 为什么不能暴力枚举所有路线很多刚接触这个问题的人第一反应是把从起点到终点的所有路径都枚举一遍挑一条最短的不就行了吗理论上没错但只对极小规模成立。假设网络有30条线路、500个站点路径数量会随着途经站数指数级增长。即使能暴力算完响应时间也完全不可控更何况出行App同一时刻要响应几十万个查询。暴力的另一个问题是人的出行需求里其实藏着最少换乘这个隐性指标纯距离最短往往不是人想要的。比如大学城到机场看起来近但需要换三次线多数人宁愿多坐两站在大站换一次。这种约束虽然也能加进穷举但会让搜索空间膨胀得更厉害。所以工程上通常把问题交给图的最短路径算法搜索过程中把代价算进去用剪枝和优先级让复杂度可控。这也是后面选择Dijkstra变体而不是枚举的根本原因不是枚举不能做而是它没法优雅地扩展到真实规模。1.3 把换乘枢纽拆成多个状态换乘是换乘算法的灵魂必须单独拎出来解剖。普通人眼里的人民广场站是一个点但在算法眼里它其实是L1线的人民广场站和L2线的人民广场站两个状态叠在一起中间有一条代价为换乘时间的虚拟连接。这个视角转换非常关键走到人民广场不叫到达你得先明确自己到底是坐L1来的还是坐L2来的。从L1下车走到L2站台是在同一个地理站点上的一次状态迁移这个迁移要付出额外代价包含步行、等车、可能的意外延误。把换乘当成状态迁移而不是原地停留是后面扩展状态Dijkstra的核心思想。它天然能回答换乘几次的问题也方便将来加入站内步行距离、换乘通道拥挤度等更精细的成本。可以说整个算法的难度不在Dijkstra本身而在于能不能把换乘这个动作建模得足够准确。2. 数据结构选型邻接表、顺序表与并集操作图模型确定后就轮到数据结构选型。这部分看起来基础实际上直接影响代码可读性和运行效率。我对每个选择都会解释一下原因避免读者照着代码敲完却不知道为什么要这样设计。2.1 稀疏图用邻接表别迷信邻接矩阵地铁网的拓扑结构是典型的稀疏图站点几百个区间边也就千把条。如果拿邻接矩阵来存500个站点就要开25万个格子其中绝大部分是无效的不可达标记白白浪费内存。更关键的是Dijkstra松弛时要遍历某个站点的所有邻居邻接矩阵每次都得扫一整行而邻接表直接顺着链表走一遍就行天然省时间。邻接表在C语言里的典型实现是顶点数组 边链表。每个顶点是一个结构体里面放着站名和一条链表的头指针链表的每个节点记录目标站点编号、线路编号、区间耗时以及指向下一条边的指针。基本形态如下typedef struct Edge { int to; // 目标站点编号 int line; // 所属线路编号 int weight; // 区间耗时单位分钟 struct Edge *next; // 下一条边 } Edge; typedef struct { char name[20]; // 站名 Edge *first; // 邻接链表头 int lineMask; // 位标记该站属于哪些线路 } Station;这里有个容易被忽略的细节每条边都要同时加入两个方向也就是从u加到v、再从v加到u否则图上会出现诡异的单向轨道。我用头插法建链表因为建图顺序不影响结果而头插法的代码最简单不用维护尾指针。lineMask这个位运算标记是给站点做线路归属快速判断用的。比如想知道人民广场是否经过2号线只需要看lineMask (1 1)是否为真O(1)就能完成不需要遍历边链表。2.2 用顺序表存站点集合顺手解决线路并集图结构负责导航但程序里还经常需要回答另一类问题1号线经过哪些站1号线和2号线一起能覆盖哪些站哪些站可以换乘。这类问题涉及的是集合运算和图遍历不是一回事得额外维护线路站点集合。C语言里最朴素的集合实现就是顺序表一个数组存元素一个整数存长度。数据量小的时候查找就用线性扫描完全够用。以500个站点、30条线路的规模为例每条线也就几十个站线性扫描每次几十次比较性能根本不是瓶颈没必要上哈希表或平衡树。顺序表最有代表性的运算就是并集。两个线路的站点并集直观理解就是坐上这两条线你总共能到达哪些站。算法很朴素先把第一个集合的元素全部复制进结果然后遍历第二个集合遇到结果里不存在的元素就追加到末尾。去重靠的是一个顺序查找避免重复项。这个操作看似基础用途却很实际。比如规划新线路时想知道它与既有线路能一起覆盖多大范围并集一下就有答案再进一步两个线路站点集合的交集恰恰就是换乘站的候选集。后面的完整代码里我专门实现了seqUnion这个函数还把两条线路的并集运行结果打印出来演示。2.3 换乘权重的设定把走路等车算进成本数据结构解决存储算法解决搜索但搜索时用的代价才是决定方案合理性的关键。地铁区间耗时我按一站3分钟来设长区间可以给4到5分钟这个弹性无所谓真正需要用心设计的是换乘惩罚。我在代码里把一次换乘的惩罚设成30分钟。这30分钟模拟了下车、步行到另一站台、等下一班车的完整过程。更重要的是它是一个给算法的明确信号能少换乘就少换乘。为什么是30而不是5因为一站才3分钟如果换乘惩罚太小算法会为了少坐一站而频繁换线给出坐一站、换一次、再坐一站这种疯子方案。30分钟足够压住这种无效换乘又不会大到让算法宁可绕一大圈也不换乘。这个值本质上是个超参数实际工程里要结合换乘通道长度、发车间隔、拥挤度动态调整但教学版本用固定值就能把原理讲透。参数取值含义区间基础耗时3分钟/站普通相邻站点行驶时间长区间耗时4-6分钟距离较长的区间单独设置换乘惩罚30分钟下车、步行、等车的综合成本3. 换乘算法的核心思路与实现细节数据结构就绪后进入算法主体。这一章不直接甩代码而是先把思路讲清楚。因为换乘算法最大的难点不是Dijkstra本身而是想清楚在一个需要换乘的图里状态到底该怎么定义。3.1 无权图用BFS带权图交给Dijkstra如果所有区间代价都是1找最少站数的路径用BFS就够了一层层往外扩第一次到达终点时的层数就是最少站数。但一旦引入换乘惩罚每条边的代价都不一样了BFS的队列就失效了——队列假设所有边代价相同先入队的先扩展代价模型复杂后这种假设不再成立。Dijkstra的核心是优先扩展当前已知距离最小的状态。维护一个未确定集合每次取出距离最小的那个用它去松弛相邻状态。因为所有边权都是正数地铁区间时间和换乘惩罚都大于0所以Dijkstra的正确性有保证一旦某个状态被标记为确定它的距离就是最终最短距离之后不会被更长的路径更新掉。朴素Dijkstra的时间复杂度是O(V²)V是状态数量。对于几百个站点的小型网络完全够用。后文在第5章讨论大规模场景下的堆优化方案那属于性能增强不影响这里的正确性。3.2 扩展状态把当前在哪条线放进搜索普通最短路径的状态就是当前位置但在换乘问题里仅仅知道我在人民广场站是不够的。我是从L1线下来的还是正坐在L2线上决定了下一步要不要付出换乘代价。同一个站点携带的线路上下文不同未来的成本就完全不同。因此必须把状态扩展成二元组(站点编号, 线路编号)。起点状态的处理要特别小心。起点站如果同时经过多条线路那么它就有多个不同的初始状态每个状态的距离都是0比如大学城, L2线是0。因为起点站上车时你既可以选择坐L2如果这个站恰好也经过L3那大学城, L3线同样可以是0。从一个状态向外扩展时规则只有两条沿着某条边走到邻站如果边的线路编号和当前状态线路相同那么代价就是边的权重如果边的线路编号不同代价就是边的权重再加上换乘惩罚。这样换乘代价被精确地嵌入在状态转移中。我不需要单独标记这里是不是换乘站只要两个连续状态的站点相同、而线路编号不同自然就知道发生了一次换乘。状态总数大约等于站点数×线路数对地铁场景来说依然很小。3.3 路径还原与换乘点识别Dijkstra运行完得到的是每个状态的最短距离。怎么还原成一条可读的出行线路办法是每个状态在距离被更新时记录前驱状态ID。我把状态ID直接编码成一个整数站点编号 * MAX_LINES 线路编号。这样做的好处是不用开结构体数组来存前驱一个二维prev数组就够了内存占用小调试打印也方便。路径还原从终点状态倒着往回走直到回到起点状态。然后把状态序列反转从头开始逐对检查相邻状态两个状态站点不同说明是乘车区间输出当前状态所在线路两个状态站点相同说明发生了换乘输出换乘后的线路。这套逻辑稳定好使而且天然能处理连续换乘的极端情况——比如某些站内跨三条线路的超级枢纽连续两个相邻状态都站点相同、线路不同就会依次输出两次换乘。4. 完整C代码实现与运行效果思路讲透了进入实操环节。这一章的代码我按模块拆开讲最后读者把它们按顺序拼接起来就是一个能编译运行的完整程序。示例网络选了几条简单线路故意不搞真实城市的复杂拓扑把注意力集中在算法本身。4.1 图结构与建图代码先建立站点和边的数据结构同时维护一个线路站点顺序表。这部分代码还包括seqUnion并集函数对应前面第2.2节讨论的内容。#include stdio.h #include stdlib.h #include string.h #define MAX_NODES 20 #define MAX_LINES 8 #define TRANSFER_PENALTY 30 #define INF 0x3f3f3f3f typedef struct Edge { int to; int line; int weight; struct Edge *next; } Edge; typedef struct { char name[20]; Edge *first; int lineMask; } Station; Station stations[MAX_NODES]; int stationCnt 0; int stRailway, stCentral, stPeople, stTech, stAirport; int stUniv, stDowntown, stSports, stOcean, stOld, stNewLib; int addStation(const char *name) { strcpy(stations[stationCnt].name, name); stations[stationCnt].first NULL; stations[stationCnt].lineMask 0; return stationCnt; } void addEdge(int u, int v, int line, int weight) { Edge *e (Edge *)malloc(sizeof(Edge)); e-to v; e-line line; e-weight weight; e-next stations[u].first; stations[u].first e; stations[u].lineMask | (1 line); e (Edge *)malloc(sizeof(Edge)); e-to u; e-line line; e-weight weight; e-next stations[v].first; stations[v].first e; stations[v].lineMask | (1 line); } void buildNetwork() { stRailway addStation(火车站); stCentral addStation(中央广场); stPeople addStation(人民广场); stTech addStation(科技园); stAirport addStation(机场); stUniv addStation(大学城); stDowntown addStation(市中心); stSports addStation(体育中心); stOcean addStation(海洋馆); stOld addStation(老城区); stNewLib addStation(新区图书馆); // 1号线火车站 - 中央广场 - 人民广场 - 科技园 - 机场 addEdge(stRailway, stCentral, 0, 3); addEdge(stCentral, stPeople, 0, 3); addEdge(stPeople, stTech, 0, 3); addEdge(stTech, stAirport, 0, 4); // 2号线大学城 - 人民广场 - 市中心 - 体育中心 - 海洋馆 addEdge(stUniv, stPeople, 1, 4); addEdge(stPeople, stDowntown, 1, 3); addEdge(stDowntown, stSports, 1, 3); addEdge(stSports, stOcean, 1, 4); // 3号线老城区 - 火车站 - 体育中心 - 新区图书馆 addEdge(stOld, stRailway, 2, 4); addEdge(stRailway, stSports, 2, 6); addEdge(stSports, stNewLib, 2, 5); }线路编号我用0、1、2分别代表1号线、2号线、3号线。代码里addEdge每次建边时同步更新两端站点的lineMask这样后面构建顺序表时不用重新遍历边直接通过位运算就能判断站点属于哪条线路。4.2 Dijkstra状态扩展与路径还原代码下面是算法的核心部分。扩展状态的技巧、路径还原、换乘次数统计都集中在这里。int dist[MAX_NODES][MAX_LINES]; int visited[MAX_NODES][MAX_LINES]; int prev[MAX_NODES][MAX_LINES]; // 存前驱状态ID-1表示没有前驱 int stateId(int s, int line) { return s * MAX_LINES line; } void dijkstra(int start) { int i, j; for (i 0; i MAX_NODES; i) { for (j 0; j MAX_LINES; j) { dist[i][j] INF; visited[i][j] 0; prev[i][j] -1; } } // 起点经过的所有线路都作为初始状态 for (j 0; j MAX_LINES; j) { if (stations[start].lineMask (1 j)) { dist[start][j] 0; } } while (1) { int bestDist INF; int bestU -1, bestLine -1; for (i 0; i MAX_NODES; i) { for (j 0; j MAX_LINES; j) { if (!visited[i][j] dist[i][j] bestDist) { bestDist dist[i][j]; bestU i; bestLine j; } } } if (bestU -1) break; visited[bestU][bestLine] 1; Edge *e; for (e stations[bestU].first; e; e e-next) { int newLine e-line; int cost e-weight; if (newLine ! bestLine) { cost TRANSFER_PENALTY; } int nd bestDist cost; if (nd dist[e-to][newLine]) { dist[e-to][newLine] nd; prev[e-to][newLine] stateId(bestU, bestLine); } } } } int findBestEndLine(int end) { int best INF; int bestLine -1; int j; for (j 0; j MAX_LINES; j) { if (dist[end][j] best) { best dist[end][j]; bestLine j; } } return bestLine; } int countTransfers(int start, int end, int endLine) { int cnt 0; int u end, line endLine; while (!(u start dist[u][line] 0)) { int pid prev[u][line]; if (pid -1) break; int pu pid / MAX_LINES; int pl pid % MAX_LINES; if (pu u pl ! line) { cnt; } u pu; line pl; } return cnt; } void printPath(int start, int end) { int endLine findBestEndLine(end); if (endLine -1 || dist[end][endLine] INF) { printf(无法到达终点站 %s\n, stations[end].name); return; } int path[MAX_NODES * MAX_LINES]; int pathLen 0; int u end, line endLine; while (!(u start dist[u][line] 0)) { path[pathLen] stateId(u, line); int pid prev[u][line]; if (pid -1) { printf(路径还原失败找不到前驱\n); return; } u pid / MAX_LINES; line pid % MAX_LINES; } path[pathLen] stateId(start, line); int i; printf(完整路径\n); for (i pathLen - 1; i 0; i--) { int su path[i] / MAX_LINES; int sl path[i] % MAX_LINES; printf(%s, stations[su].name); if (i 0) { int nu path[i - 1] / MAX_LINES; int nl path[i - 1] % MAX_LINES; if (nu ! su) { printf( --(L%d线)-- , sl 1); } else { printf( --换乘L%d线-- , nl 1); } } else { printf(\n); } } int firstLine path[pathLen - 1] % MAX_LINES; printf(\n出行方案\n); printf(从 %s 乘坐L%d线\n, stations[start].name, firstLine 1); for (i pathLen - 2; i 0; i--) { int su path[i] / MAX_LINES; int sl path[i] % MAX_LINES; int pu path[i 1] / MAX_LINES; int pl path[i 1] % MAX_LINES; if (su pu sl ! pl) { printf(在 %s 换乘L%d线\n, stations[su].name, sl 1); } } printf(到达终点 %s全程耗时约 %d 分钟换乘 %d 次\n, stations[end].name, dist[end][endLine], countTransfers(start, end, endLine)); }stateId把二维状态压成一维整数prev数组里存的全是这种ID。路径还原时再用除法和取模拆回站点编号和线路编号。这个状态压缩的小技巧能让代码结构保持紧凑同时又足够直观。4.3 顺序表并集实现与主函数最后是顺序表实现、线路站点集合构建、以及两组查询的入口。typedef struct { int data[MAX_NODES]; int len; } SeqList; int seqFind(SeqList *list, int x) { int i; for (i 0; i list-len; i) { if (list-data[i] x) return i; } return -1; } void seqUnion(SeqList *a, SeqList *b, SeqList *result) { result-len 0; int i; for (i 0; i a-len; i) { result-data[result-len] a-data[i]; } for (i 0; i b-len; i) { if (seqFind(result, b-data[i]) -1) { result-data[result-len] b-data[i]; } } } void printSeqList(SeqList *list) { int i; printf({ ); for (i 0; i list-len; i) { printf(%s%s, stations[list-data[i]].name, i list-len - 1 ? : , ); } printf(}\n); } void buildLineSets(SeqList *lineSets) { int i, j; for (i 0; i MAX_LINES; i) { lineSets[i].len 0; } for (i 0; i stationCnt; i) { for (j 0; j MAX_LINES; j) { if (stations[i].lineMask (1 j)) { lineSets[j].data[lineSets[j].len] i; } } } } int main() { buildNetwork(); SeqList lineSets[MAX_LINES]; buildLineSets(lineSets); printf(1号线站点); printSeqList(lineSets[0]); printf(2号线站点); printSeqList(lineSets[1]); printf(3号线站点); printSeqList(lineSets[2]); SeqList unionRes; seqUnion(lineSets[0], lineSets[1], unionRes); printf(1、2号线站点并集); printSeqList(unionRes); printf(\n--- 查询1大学城 - 人民广场 ---\n); dijkstra(stUniv); printPath(stUniv, stPeople); printf(\n--- 查询2大学城 - 机场 ---\n); dijkstra(stUniv); printPath(stUniv, stAirport); printf(\n--- 查询3老城区 - 海洋馆 ---\n); dijkstra(stOld); printPath(stOld, stOcean); return 0; }buildLineSets根据lineMask把每个站归入对应线路的集合本质上是对图信息的一次轻量聚合。seqUnion就是前面讨论的并集实现先复制再查重逻辑简单但完整。4.4 运行结果与过程分析把上面代码按顺序拼接编译运行后会得到类似下面的输出1号线站点{ 机场, 科技园, 人民广场, 中央广场, 火车站 } 2号线站点{ 海洋馆, 体育中心, 市中心, 人民广场, 大学城 } 3号线站点{ 新区图书馆, 体育中心, 火车站, 老城区 } 1、2号线站点并集{ 机场, 科技园, 人民广场, 中央广场, 火车站, 海洋馆, 体育中心, 市中心, 大学城 } --- 查询1大学城 - 人民广场 --- 完整路径 大学城 --(L2线)-- 人民广场 出行方案 从 大学城 乘坐L2线 到达终点 人民广场全程耗时约 4 分钟换乘 0 次 --- 查询2大学城 - 机场 --- 完整路径 大学城 --(L2线)-- 人民广场 --换乘L1线-- 科技园 --(L1线)-- 机场 出行方案 从 大学城 乘坐L2线 在 人民广场 换乘L1线 到达终点 机场全程耗时约 41 分钟换乘 1 次 --- 查询3老城区 - 海洋馆 --- 完整路径 老城区 --(L3线)-- 火车站 --(L3线)-- 体育中心 --换乘L2线-- 海洋馆 出行方案 从 老城区 乘坐L3线 在 体育中心 换乘L2线 到达终点 海洋馆全程耗时约 44 分钟换乘 1 次这几个结果各有代表性。查询1是直达场景验证基础路径输出查询2是典型的一次换乘算法在人民广场准确识别换乘点最有意思的是查询3老城区去海洋馆理论上可以走老城区→火车站→人民广场→市中心→体育中心→海洋馆这条绕远路线但算法选择了在体育中心直接换乘全程只需要44分钟比绕去人民广场的方案节省大量时间。这就是换乘惩罚权重在起作用它让算法在多坐几站和换一次线之间做出了理性判断。5. 实测中的坑与优化方向代码跑通只是第一步真正在真实工程里落地时还有一堆细节会咬人。这一章记录我实际踩过的坑和对应的解决经验全是教科书里不太会写的东西。5.1 双向边、环线与lineMask的边界最基础也最容易翻车的是双向边漏加。addEdge里如果只加一个方向Dijkstra搜出来的路径就是单向可达看起来像地铁线路只允许单向乘坐非常诡异。我自己的习惯是写完建图函数后先打印每个站点的邻接表肉眼扫一遍确认每个区间都出现了两次。环线是另一个隐蔽的坑。环线是首尾相接的如果不把最后一站和第一站之间的边加上环线就被硬生生切成了一段断头路绕一圈坐回原点的合法路径会永远搜不到。示例网络里虽然没有环线但真实城市基本都有建图时必须留意。lineMask的位移操作也有边界问题。我用1 line标记线路归属如果实际线路数小于MAX_LINES没问题但如果线路编号超出MAX_LINES位移就会越界导致未定义行为。所以MAX_LINES必须留足余量或者在建图时加一个线路编号合法性断言。5.2 大规模网络的性能优化方向朴素Dijkstra在示例规模下毫秒级完成但真实城市的地铁网络站点多、线路密、查询频率高必须做优化。最直接的优化是用优先队列小顶堆替代每次线性扫描找最小状态复杂度从O(V²)降到O(E log V)。E是状态之间可达边的数量。在这个算法里V约等于站点数×线路数E约等于边数×线路数规模依然是可控的。更进一步的做法包括双向Dijkstra从起点和终点同时搜两个方向在中途相遇即可停止。对单次查询能省一半左右的时间。A*启发式搜索引入当前站到终点站的直线距离作为启发函数让搜索更有方向性。预处理换乘表如果是固定的离线地图可以提前把热门站对之间的最优路径算好查询时直接查表响应时间近乎零。工程系统里通常不是只跑一个Dijkstra就完事而是叠加了多种策略。但不管怎么叠核心思想仍然是从状态定义出发控制搜索空间。5.3 调试心得与几个实用建议最后分享几条我在调试这类代码时总结出的经验每一条都是真实换来的教训。调试时先打印前驱表。如果某个终点状态的距离合理但prev值指向了一个根本不存在的状态ID十有八九是状态ID的编码和解码没对齐。建议单独写一个printf(state %d - %d\n)的调试辅助函数逐条核对。INF的取值要当心。不要用INT_MAX当无穷大因为松弛操作里有bestDist cost一旦bestDist取到INT_MAX加上任何正数都会溢出成负数距离比较瞬间乱套。我用的是0x3f3f3f3f约等于10.7亿足够大又不会溢出。测试用例要从简单到复杂逐级递进先测直达再测一次换乘再测多次换乘最后测起点和终点不可达的情况。终点站没有任何线路经过是一个容易被忽略的输入但用户完全可能输入一个不存在的站点名。代码里findBestEndLine返回-1就是处理的这个场景。另外建议给每个站点加一个英文编号甚至拼音缩写调试打印时用中文站名虽然直观但在终端里对齐困难容易出现排版错乱。我就是因为贪图中文站名好看调试时多花了半小时去对齐表格。
C语言实现地铁换乘算法：基于Dijkstra扩展状态的图论实战
1. 先把怎么走翻译成图论问题“人民广场怎么走”这种问题日常交给手机地图就够了。但我自己作为一个写代码的人更喜欢把它当成一个算法题来拆给定一张城市地铁网、一个起点站、一个终点站程序要自己算出该怎么坐、在哪换、换几次。回答这个问题的底层核心就是地铁换乘算法。这篇文章聊的不是某个商业App的完整方案而是一个用C语言就能实现的迷你换乘引擎。我会完整走一遍从图建模、数据结构选型、Dijkstra变体设计到代码实作的全过程同时把换乘次数换乘时间这类现实约束翻译成算法里的权重。文章最后会给出可以直接编译运行的完整C代码以及几组真实查询的运行结果。适合两类人看一类是刚学完数据结构、想看看最短路径算法怎么落地的新手另一类是想在项目里快速做一个轻量级出行路线模块、又不想引入重量级依赖的开发者。看完至少能自己扩展出带首末班时间、带站点实时客流等功能的换乘原型。1.1 站点是点、区间是边一张地铁网的图模型要把人民广场怎么走交给程序第一步就是把地铁网变成程序认识的东西。最自然的建模方式是把地铁网抽象成一张无向图。站点是顶点相邻两站之间的轨道区间是边。每条边至少携带三个信息两端站点、属于哪条线路、跑完这个区间要多久。换乘站呢就是一个同时被多条线路共用的顶点。打个比方把地铁图想成一张只能沿着轨道走的旅游地图你从大学城走去火车站唯一能走的路就是图上画出来的轨道区间走到交叉口换乘站时你可以从一条轨道换到另一条轨道前提是付出一点额外体力——在真实世界里就是下车、走路、等车。这个抽象的价值在于它把人民广场怎么走从一个日常问路问题变成了一个数学问题在带权无向图中找一条从起点站到终点站的代价最小路径。一旦完成这个翻译后面所有算法都有章可循。无向图的选择也有讲究。绝大多数地铁线路是双向运行的所以每添加一个区间都要同时建立两个方向的边。如果漏掉反方向算法就会跑出坐过站之后回不去这种反人类结果。环线也不特殊它只是两条边首尾相接形成闭合建模方式没有任何额外负担。1.2 为什么不能暴力枚举所有路线很多刚接触这个问题的人第一反应是把从起点到终点的所有路径都枚举一遍挑一条最短的不就行了吗理论上没错但只对极小规模成立。假设网络有30条线路、500个站点路径数量会随着途经站数指数级增长。即使能暴力算完响应时间也完全不可控更何况出行App同一时刻要响应几十万个查询。暴力的另一个问题是人的出行需求里其实藏着最少换乘这个隐性指标纯距离最短往往不是人想要的。比如大学城到机场看起来近但需要换三次线多数人宁愿多坐两站在大站换一次。这种约束虽然也能加进穷举但会让搜索空间膨胀得更厉害。所以工程上通常把问题交给图的最短路径算法搜索过程中把代价算进去用剪枝和优先级让复杂度可控。这也是后面选择Dijkstra变体而不是枚举的根本原因不是枚举不能做而是它没法优雅地扩展到真实规模。1.3 把换乘枢纽拆成多个状态换乘是换乘算法的灵魂必须单独拎出来解剖。普通人眼里的人民广场站是一个点但在算法眼里它其实是L1线的人民广场站和L2线的人民广场站两个状态叠在一起中间有一条代价为换乘时间的虚拟连接。这个视角转换非常关键走到人民广场不叫到达你得先明确自己到底是坐L1来的还是坐L2来的。从L1下车走到L2站台是在同一个地理站点上的一次状态迁移这个迁移要付出额外代价包含步行、等车、可能的意外延误。把换乘当成状态迁移而不是原地停留是后面扩展状态Dijkstra的核心思想。它天然能回答换乘几次的问题也方便将来加入站内步行距离、换乘通道拥挤度等更精细的成本。可以说整个算法的难度不在Dijkstra本身而在于能不能把换乘这个动作建模得足够准确。2. 数据结构选型邻接表、顺序表与并集操作图模型确定后就轮到数据结构选型。这部分看起来基础实际上直接影响代码可读性和运行效率。我对每个选择都会解释一下原因避免读者照着代码敲完却不知道为什么要这样设计。2.1 稀疏图用邻接表别迷信邻接矩阵地铁网的拓扑结构是典型的稀疏图站点几百个区间边也就千把条。如果拿邻接矩阵来存500个站点就要开25万个格子其中绝大部分是无效的不可达标记白白浪费内存。更关键的是Dijkstra松弛时要遍历某个站点的所有邻居邻接矩阵每次都得扫一整行而邻接表直接顺着链表走一遍就行天然省时间。邻接表在C语言里的典型实现是顶点数组 边链表。每个顶点是一个结构体里面放着站名和一条链表的头指针链表的每个节点记录目标站点编号、线路编号、区间耗时以及指向下一条边的指针。基本形态如下typedef struct Edge { int to; // 目标站点编号 int line; // 所属线路编号 int weight; // 区间耗时单位分钟 struct Edge *next; // 下一条边 } Edge; typedef struct { char name[20]; // 站名 Edge *first; // 邻接链表头 int lineMask; // 位标记该站属于哪些线路 } Station;这里有个容易被忽略的细节每条边都要同时加入两个方向也就是从u加到v、再从v加到u否则图上会出现诡异的单向轨道。我用头插法建链表因为建图顺序不影响结果而头插法的代码最简单不用维护尾指针。lineMask这个位运算标记是给站点做线路归属快速判断用的。比如想知道人民广场是否经过2号线只需要看lineMask (1 1)是否为真O(1)就能完成不需要遍历边链表。2.2 用顺序表存站点集合顺手解决线路并集图结构负责导航但程序里还经常需要回答另一类问题1号线经过哪些站1号线和2号线一起能覆盖哪些站哪些站可以换乘。这类问题涉及的是集合运算和图遍历不是一回事得额外维护线路站点集合。C语言里最朴素的集合实现就是顺序表一个数组存元素一个整数存长度。数据量小的时候查找就用线性扫描完全够用。以500个站点、30条线路的规模为例每条线也就几十个站线性扫描每次几十次比较性能根本不是瓶颈没必要上哈希表或平衡树。顺序表最有代表性的运算就是并集。两个线路的站点并集直观理解就是坐上这两条线你总共能到达哪些站。算法很朴素先把第一个集合的元素全部复制进结果然后遍历第二个集合遇到结果里不存在的元素就追加到末尾。去重靠的是一个顺序查找避免重复项。这个操作看似基础用途却很实际。比如规划新线路时想知道它与既有线路能一起覆盖多大范围并集一下就有答案再进一步两个线路站点集合的交集恰恰就是换乘站的候选集。后面的完整代码里我专门实现了seqUnion这个函数还把两条线路的并集运行结果打印出来演示。2.3 换乘权重的设定把走路等车算进成本数据结构解决存储算法解决搜索但搜索时用的代价才是决定方案合理性的关键。地铁区间耗时我按一站3分钟来设长区间可以给4到5分钟这个弹性无所谓真正需要用心设计的是换乘惩罚。我在代码里把一次换乘的惩罚设成30分钟。这30分钟模拟了下车、步行到另一站台、等下一班车的完整过程。更重要的是它是一个给算法的明确信号能少换乘就少换乘。为什么是30而不是5因为一站才3分钟如果换乘惩罚太小算法会为了少坐一站而频繁换线给出坐一站、换一次、再坐一站这种疯子方案。30分钟足够压住这种无效换乘又不会大到让算法宁可绕一大圈也不换乘。这个值本质上是个超参数实际工程里要结合换乘通道长度、发车间隔、拥挤度动态调整但教学版本用固定值就能把原理讲透。参数取值含义区间基础耗时3分钟/站普通相邻站点行驶时间长区间耗时4-6分钟距离较长的区间单独设置换乘惩罚30分钟下车、步行、等车的综合成本3. 换乘算法的核心思路与实现细节数据结构就绪后进入算法主体。这一章不直接甩代码而是先把思路讲清楚。因为换乘算法最大的难点不是Dijkstra本身而是想清楚在一个需要换乘的图里状态到底该怎么定义。3.1 无权图用BFS带权图交给Dijkstra如果所有区间代价都是1找最少站数的路径用BFS就够了一层层往外扩第一次到达终点时的层数就是最少站数。但一旦引入换乘惩罚每条边的代价都不一样了BFS的队列就失效了——队列假设所有边代价相同先入队的先扩展代价模型复杂后这种假设不再成立。Dijkstra的核心是优先扩展当前已知距离最小的状态。维护一个未确定集合每次取出距离最小的那个用它去松弛相邻状态。因为所有边权都是正数地铁区间时间和换乘惩罚都大于0所以Dijkstra的正确性有保证一旦某个状态被标记为确定它的距离就是最终最短距离之后不会被更长的路径更新掉。朴素Dijkstra的时间复杂度是O(V²)V是状态数量。对于几百个站点的小型网络完全够用。后文在第5章讨论大规模场景下的堆优化方案那属于性能增强不影响这里的正确性。3.2 扩展状态把当前在哪条线放进搜索普通最短路径的状态就是当前位置但在换乘问题里仅仅知道我在人民广场站是不够的。我是从L1线下来的还是正坐在L2线上决定了下一步要不要付出换乘代价。同一个站点携带的线路上下文不同未来的成本就完全不同。因此必须把状态扩展成二元组(站点编号, 线路编号)。起点状态的处理要特别小心。起点站如果同时经过多条线路那么它就有多个不同的初始状态每个状态的距离都是0比如大学城, L2线是0。因为起点站上车时你既可以选择坐L2如果这个站恰好也经过L3那大学城, L3线同样可以是0。从一个状态向外扩展时规则只有两条沿着某条边走到邻站如果边的线路编号和当前状态线路相同那么代价就是边的权重如果边的线路编号不同代价就是边的权重再加上换乘惩罚。这样换乘代价被精确地嵌入在状态转移中。我不需要单独标记这里是不是换乘站只要两个连续状态的站点相同、而线路编号不同自然就知道发生了一次换乘。状态总数大约等于站点数×线路数对地铁场景来说依然很小。3.3 路径还原与换乘点识别Dijkstra运行完得到的是每个状态的最短距离。怎么还原成一条可读的出行线路办法是每个状态在距离被更新时记录前驱状态ID。我把状态ID直接编码成一个整数站点编号 * MAX_LINES 线路编号。这样做的好处是不用开结构体数组来存前驱一个二维prev数组就够了内存占用小调试打印也方便。路径还原从终点状态倒着往回走直到回到起点状态。然后把状态序列反转从头开始逐对检查相邻状态两个状态站点不同说明是乘车区间输出当前状态所在线路两个状态站点相同说明发生了换乘输出换乘后的线路。这套逻辑稳定好使而且天然能处理连续换乘的极端情况——比如某些站内跨三条线路的超级枢纽连续两个相邻状态都站点相同、线路不同就会依次输出两次换乘。4. 完整C代码实现与运行效果思路讲透了进入实操环节。这一章的代码我按模块拆开讲最后读者把它们按顺序拼接起来就是一个能编译运行的完整程序。示例网络选了几条简单线路故意不搞真实城市的复杂拓扑把注意力集中在算法本身。4.1 图结构与建图代码先建立站点和边的数据结构同时维护一个线路站点顺序表。这部分代码还包括seqUnion并集函数对应前面第2.2节讨论的内容。#include stdio.h #include stdlib.h #include string.h #define MAX_NODES 20 #define MAX_LINES 8 #define TRANSFER_PENALTY 30 #define INF 0x3f3f3f3f typedef struct Edge { int to; int line; int weight; struct Edge *next; } Edge; typedef struct { char name[20]; Edge *first; int lineMask; } Station; Station stations[MAX_NODES]; int stationCnt 0; int stRailway, stCentral, stPeople, stTech, stAirport; int stUniv, stDowntown, stSports, stOcean, stOld, stNewLib; int addStation(const char *name) { strcpy(stations[stationCnt].name, name); stations[stationCnt].first NULL; stations[stationCnt].lineMask 0; return stationCnt; } void addEdge(int u, int v, int line, int weight) { Edge *e (Edge *)malloc(sizeof(Edge)); e-to v; e-line line; e-weight weight; e-next stations[u].first; stations[u].first e; stations[u].lineMask | (1 line); e (Edge *)malloc(sizeof(Edge)); e-to u; e-line line; e-weight weight; e-next stations[v].first; stations[v].first e; stations[v].lineMask | (1 line); } void buildNetwork() { stRailway addStation(火车站); stCentral addStation(中央广场); stPeople addStation(人民广场); stTech addStation(科技园); stAirport addStation(机场); stUniv addStation(大学城); stDowntown addStation(市中心); stSports addStation(体育中心); stOcean addStation(海洋馆); stOld addStation(老城区); stNewLib addStation(新区图书馆); // 1号线火车站 - 中央广场 - 人民广场 - 科技园 - 机场 addEdge(stRailway, stCentral, 0, 3); addEdge(stCentral, stPeople, 0, 3); addEdge(stPeople, stTech, 0, 3); addEdge(stTech, stAirport, 0, 4); // 2号线大学城 - 人民广场 - 市中心 - 体育中心 - 海洋馆 addEdge(stUniv, stPeople, 1, 4); addEdge(stPeople, stDowntown, 1, 3); addEdge(stDowntown, stSports, 1, 3); addEdge(stSports, stOcean, 1, 4); // 3号线老城区 - 火车站 - 体育中心 - 新区图书馆 addEdge(stOld, stRailway, 2, 4); addEdge(stRailway, stSports, 2, 6); addEdge(stSports, stNewLib, 2, 5); }线路编号我用0、1、2分别代表1号线、2号线、3号线。代码里addEdge每次建边时同步更新两端站点的lineMask这样后面构建顺序表时不用重新遍历边直接通过位运算就能判断站点属于哪条线路。4.2 Dijkstra状态扩展与路径还原代码下面是算法的核心部分。扩展状态的技巧、路径还原、换乘次数统计都集中在这里。int dist[MAX_NODES][MAX_LINES]; int visited[MAX_NODES][MAX_LINES]; int prev[MAX_NODES][MAX_LINES]; // 存前驱状态ID-1表示没有前驱 int stateId(int s, int line) { return s * MAX_LINES line; } void dijkstra(int start) { int i, j; for (i 0; i MAX_NODES; i) { for (j 0; j MAX_LINES; j) { dist[i][j] INF; visited[i][j] 0; prev[i][j] -1; } } // 起点经过的所有线路都作为初始状态 for (j 0; j MAX_LINES; j) { if (stations[start].lineMask (1 j)) { dist[start][j] 0; } } while (1) { int bestDist INF; int bestU -1, bestLine -1; for (i 0; i MAX_NODES; i) { for (j 0; j MAX_LINES; j) { if (!visited[i][j] dist[i][j] bestDist) { bestDist dist[i][j]; bestU i; bestLine j; } } } if (bestU -1) break; visited[bestU][bestLine] 1; Edge *e; for (e stations[bestU].first; e; e e-next) { int newLine e-line; int cost e-weight; if (newLine ! bestLine) { cost TRANSFER_PENALTY; } int nd bestDist cost; if (nd dist[e-to][newLine]) { dist[e-to][newLine] nd; prev[e-to][newLine] stateId(bestU, bestLine); } } } } int findBestEndLine(int end) { int best INF; int bestLine -1; int j; for (j 0; j MAX_LINES; j) { if (dist[end][j] best) { best dist[end][j]; bestLine j; } } return bestLine; } int countTransfers(int start, int end, int endLine) { int cnt 0; int u end, line endLine; while (!(u start dist[u][line] 0)) { int pid prev[u][line]; if (pid -1) break; int pu pid / MAX_LINES; int pl pid % MAX_LINES; if (pu u pl ! line) { cnt; } u pu; line pl; } return cnt; } void printPath(int start, int end) { int endLine findBestEndLine(end); if (endLine -1 || dist[end][endLine] INF) { printf(无法到达终点站 %s\n, stations[end].name); return; } int path[MAX_NODES * MAX_LINES]; int pathLen 0; int u end, line endLine; while (!(u start dist[u][line] 0)) { path[pathLen] stateId(u, line); int pid prev[u][line]; if (pid -1) { printf(路径还原失败找不到前驱\n); return; } u pid / MAX_LINES; line pid % MAX_LINES; } path[pathLen] stateId(start, line); int i; printf(完整路径\n); for (i pathLen - 1; i 0; i--) { int su path[i] / MAX_LINES; int sl path[i] % MAX_LINES; printf(%s, stations[su].name); if (i 0) { int nu path[i - 1] / MAX_LINES; int nl path[i - 1] % MAX_LINES; if (nu ! su) { printf( --(L%d线)-- , sl 1); } else { printf( --换乘L%d线-- , nl 1); } } else { printf(\n); } } int firstLine path[pathLen - 1] % MAX_LINES; printf(\n出行方案\n); printf(从 %s 乘坐L%d线\n, stations[start].name, firstLine 1); for (i pathLen - 2; i 0; i--) { int su path[i] / MAX_LINES; int sl path[i] % MAX_LINES; int pu path[i 1] / MAX_LINES; int pl path[i 1] % MAX_LINES; if (su pu sl ! pl) { printf(在 %s 换乘L%d线\n, stations[su].name, sl 1); } } printf(到达终点 %s全程耗时约 %d 分钟换乘 %d 次\n, stations[end].name, dist[end][endLine], countTransfers(start, end, endLine)); }stateId把二维状态压成一维整数prev数组里存的全是这种ID。路径还原时再用除法和取模拆回站点编号和线路编号。这个状态压缩的小技巧能让代码结构保持紧凑同时又足够直观。4.3 顺序表并集实现与主函数最后是顺序表实现、线路站点集合构建、以及两组查询的入口。typedef struct { int data[MAX_NODES]; int len; } SeqList; int seqFind(SeqList *list, int x) { int i; for (i 0; i list-len; i) { if (list-data[i] x) return i; } return -1; } void seqUnion(SeqList *a, SeqList *b, SeqList *result) { result-len 0; int i; for (i 0; i a-len; i) { result-data[result-len] a-data[i]; } for (i 0; i b-len; i) { if (seqFind(result, b-data[i]) -1) { result-data[result-len] b-data[i]; } } } void printSeqList(SeqList *list) { int i; printf({ ); for (i 0; i list-len; i) { printf(%s%s, stations[list-data[i]].name, i list-len - 1 ? : , ); } printf(}\n); } void buildLineSets(SeqList *lineSets) { int i, j; for (i 0; i MAX_LINES; i) { lineSets[i].len 0; } for (i 0; i stationCnt; i) { for (j 0; j MAX_LINES; j) { if (stations[i].lineMask (1 j)) { lineSets[j].data[lineSets[j].len] i; } } } } int main() { buildNetwork(); SeqList lineSets[MAX_LINES]; buildLineSets(lineSets); printf(1号线站点); printSeqList(lineSets[0]); printf(2号线站点); printSeqList(lineSets[1]); printf(3号线站点); printSeqList(lineSets[2]); SeqList unionRes; seqUnion(lineSets[0], lineSets[1], unionRes); printf(1、2号线站点并集); printSeqList(unionRes); printf(\n--- 查询1大学城 - 人民广场 ---\n); dijkstra(stUniv); printPath(stUniv, stPeople); printf(\n--- 查询2大学城 - 机场 ---\n); dijkstra(stUniv); printPath(stUniv, stAirport); printf(\n--- 查询3老城区 - 海洋馆 ---\n); dijkstra(stOld); printPath(stOld, stOcean); return 0; }buildLineSets根据lineMask把每个站归入对应线路的集合本质上是对图信息的一次轻量聚合。seqUnion就是前面讨论的并集实现先复制再查重逻辑简单但完整。4.4 运行结果与过程分析把上面代码按顺序拼接编译运行后会得到类似下面的输出1号线站点{ 机场, 科技园, 人民广场, 中央广场, 火车站 } 2号线站点{ 海洋馆, 体育中心, 市中心, 人民广场, 大学城 } 3号线站点{ 新区图书馆, 体育中心, 火车站, 老城区 } 1、2号线站点并集{ 机场, 科技园, 人民广场, 中央广场, 火车站, 海洋馆, 体育中心, 市中心, 大学城 } --- 查询1大学城 - 人民广场 --- 完整路径 大学城 --(L2线)-- 人民广场 出行方案 从 大学城 乘坐L2线 到达终点 人民广场全程耗时约 4 分钟换乘 0 次 --- 查询2大学城 - 机场 --- 完整路径 大学城 --(L2线)-- 人民广场 --换乘L1线-- 科技园 --(L1线)-- 机场 出行方案 从 大学城 乘坐L2线 在 人民广场 换乘L1线 到达终点 机场全程耗时约 41 分钟换乘 1 次 --- 查询3老城区 - 海洋馆 --- 完整路径 老城区 --(L3线)-- 火车站 --(L3线)-- 体育中心 --换乘L2线-- 海洋馆 出行方案 从 老城区 乘坐L3线 在 体育中心 换乘L2线 到达终点 海洋馆全程耗时约 44 分钟换乘 1 次这几个结果各有代表性。查询1是直达场景验证基础路径输出查询2是典型的一次换乘算法在人民广场准确识别换乘点最有意思的是查询3老城区去海洋馆理论上可以走老城区→火车站→人民广场→市中心→体育中心→海洋馆这条绕远路线但算法选择了在体育中心直接换乘全程只需要44分钟比绕去人民广场的方案节省大量时间。这就是换乘惩罚权重在起作用它让算法在多坐几站和换一次线之间做出了理性判断。5. 实测中的坑与优化方向代码跑通只是第一步真正在真实工程里落地时还有一堆细节会咬人。这一章记录我实际踩过的坑和对应的解决经验全是教科书里不太会写的东西。5.1 双向边、环线与lineMask的边界最基础也最容易翻车的是双向边漏加。addEdge里如果只加一个方向Dijkstra搜出来的路径就是单向可达看起来像地铁线路只允许单向乘坐非常诡异。我自己的习惯是写完建图函数后先打印每个站点的邻接表肉眼扫一遍确认每个区间都出现了两次。环线是另一个隐蔽的坑。环线是首尾相接的如果不把最后一站和第一站之间的边加上环线就被硬生生切成了一段断头路绕一圈坐回原点的合法路径会永远搜不到。示例网络里虽然没有环线但真实城市基本都有建图时必须留意。lineMask的位移操作也有边界问题。我用1 line标记线路归属如果实际线路数小于MAX_LINES没问题但如果线路编号超出MAX_LINES位移就会越界导致未定义行为。所以MAX_LINES必须留足余量或者在建图时加一个线路编号合法性断言。5.2 大规模网络的性能优化方向朴素Dijkstra在示例规模下毫秒级完成但真实城市的地铁网络站点多、线路密、查询频率高必须做优化。最直接的优化是用优先队列小顶堆替代每次线性扫描找最小状态复杂度从O(V²)降到O(E log V)。E是状态之间可达边的数量。在这个算法里V约等于站点数×线路数E约等于边数×线路数规模依然是可控的。更进一步的做法包括双向Dijkstra从起点和终点同时搜两个方向在中途相遇即可停止。对单次查询能省一半左右的时间。A*启发式搜索引入当前站到终点站的直线距离作为启发函数让搜索更有方向性。预处理换乘表如果是固定的离线地图可以提前把热门站对之间的最优路径算好查询时直接查表响应时间近乎零。工程系统里通常不是只跑一个Dijkstra就完事而是叠加了多种策略。但不管怎么叠核心思想仍然是从状态定义出发控制搜索空间。5.3 调试心得与几个实用建议最后分享几条我在调试这类代码时总结出的经验每一条都是真实换来的教训。调试时先打印前驱表。如果某个终点状态的距离合理但prev值指向了一个根本不存在的状态ID十有八九是状态ID的编码和解码没对齐。建议单独写一个printf(state %d - %d\n)的调试辅助函数逐条核对。INF的取值要当心。不要用INT_MAX当无穷大因为松弛操作里有bestDist cost一旦bestDist取到INT_MAX加上任何正数都会溢出成负数距离比较瞬间乱套。我用的是0x3f3f3f3f约等于10.7亿足够大又不会溢出。测试用例要从简单到复杂逐级递进先测直达再测一次换乘再测多次换乘最后测起点和终点不可达的情况。终点站没有任何线路经过是一个容易被忽略的输入但用户完全可能输入一个不存在的站点名。代码里findBestEndLine返回-1就是处理的这个场景。另外建议给每个站点加一个英文编号甚至拼音缩写调试打印时用中文站名虽然直观但在终端里对齐困难容易出现排版错乱。我就是因为贪图中文站名好看调试时多花了半小时去对齐表格。