“人民广场怎么走”这句话我在上海被问过无数次每次回答完都会多想一层如果让我用程序来回答应该怎么写把整个地铁网络数据交给计算机让它从任意站点算出一条去人民广场的最优路线——这就是一个典型的地铁换乘算法问题。地铁网络本质是一张带权图站点是节点两个站点之间的隧道是边换乘行为则是边上的额外代价。最优路径的定义还不止一种有人要换乘次数最少有人要总耗时最短有人还希望步行距离尽量短。这篇文章不打算只讲理论我直接把完整的建模思路、数据结构选型、BFS/Dijkstra/A* 的取舍以及一份能跑起来的 C 语言实现全部拆开讲。适合正在学图算法的人、准备算法面试的开发者或者想在导航类软件里做路线规划的同学参考。1. 问题拆解从“问路”到“图论建模”1.1 把地铁运营图变成程序能理解的图站在用户视角“人民广场怎么走”是一句话的事但落到代码里第一件事是确定“图”的形态。地铁网络有站点、有区间线路最自然的方式是把每个站点当作一个节点相邻两个站点之间的区间当作一条边边上记录乘车耗时。但这里有个细节一条地铁线路上的两个站之间通常有上下行两个方向运行时间基本一致所以建模时可以用无向边或者拆成两条方向相反的有向边。我更推荐用两条有向边来表示好处是以后做实时客流、单向运营调整时不用改动图结构。节点和边的数据从哪来国内城市地铁官网会公布站点和首末班时间但要拿到精确到分钟的区间运行时间一般得靠运营数据整理。自己项目用的话可以用开源社区维护的 GTFS 数据里面已经包含 trips、stop_times、transfers 等表解析出来就能建图。个人练手可以在代码里硬编码一个简化的小网络比如只保留 1、2、8 号线的十来个站点数据量小调试起来也方便。要注意的是地铁图里“边权”不能只用距离。两站之间的运行时间才是真正影响体验的指标所以我会用“分钟”作为边的权重单位这个值可以根据官方时刻表推算也可以用站间距离除以平均旅行速度估算。换乘站的内部步行时间则作为换乘时的附加权重单独处理。1.2 换乘方案的评价维度不止一个同样的起终点不同乘客想要的结果完全不同。最少换乘次数适合拿了很多行李、不想上上下下的乘客。最短总时间把乘车时间加上换乘步行时间求一个全局最小。最少步行距离这需要给每条换乘通道单独建模复杂度更高。现实中的规划应用基本都是多目标权衡但作为算法入门我更建议先把“最少换乘”和“最短时间”这两个目标分别实现再考虑组合。这里有一个非常关键的认知最少换乘不等于最短时间。举个例子从某个郊区站到人民广场可能坐慢线直达只需要换乘 0 次但耗时 50 分钟而坐快线换乘 1 次只要 35 分钟。如果只做最少换乘的 BFS得到的结果不是时间最优的如果只做最短时间的 Dijkstra换乘次数可能比较多。所以在设计算法之前得先明确你的“最优”到底是什么。真要做一个完整的地铁导航通常的做法是在 Dijkstra 的边权上叠加“换乘惩罚时间”通过调节惩罚系数来平衡换乘次数和总耗时。2. 数据结构设计先管好站点再管好边2.1 用顺序表维护全局站点表写 C 语言实现时我习惯先维护一个全局站点表。因为所有节点编号、名字、所属线路信息都要频繁查询顺序表动态数组是首选。为什么不用链表因为建图和路径还原时经常要按下标随机访问站点信息链表只能从头遍历在站点数量上千之后效率很难看。顺序表现在几乎所有场景都是更合理的选择。顺序表的结构一般长这样#define MAX_STATIONS 1024 typedef struct { int id; char name[32]; } Station; typedef struct { Station data[MAX_STATIONS]; int length; } StationSeqList;添加新站点时只需要在尾部追加这其实就是“顺序表尾插法”。如果站点 ID 不连续我会加一个简单的映射函数把外部站点 ID 转换成内部数组下标。顺带一提之前在别的项目里写“用顺序表求两个集合的并集”本质上也是同样的思路先开一个足够大的数组遍历集合 A 全部放入遍历集合 B 时检查是否已存在不存在就尾插。地铁建图时把多条线路的站点合并到一张全局站点表做的事情和求并集一模一样。需要注意顺序表扩容不能每次只扩一个位置。写死 MAX_STATIONS 对练手够用但工程化时应该实现 realloc 方式的动态扩容扩容策略一般按倍数扩展避免频繁拷贝。2.2 邻接表与邻接矩阵的取舍图有两种经典存储方式邻接矩阵和邻接表。地铁网络的节点数几百到几千不算大边数也不多每个站点平均只有两三条边属于典型的稀疏图。如果用邻接矩阵存 1000 个站点就要 1000×1000 个 int而且大部分位置都是无穷大空间浪费严重。所以我选邻接表。邻接表用链表存储每个节点的邻居结构如下typedef struct EdgeNode { int to; // 目标节点编号 int line; // 这条边属于哪条地铁线 int weight; // 运行时间单位分钟 struct EdgeNode *next; } EdgeNode; typedef struct { EdgeNode *first; } AdjList;这里每条边都带一个 line 字段这个字段在判断换乘时非常重要。它记录了从当前站点到目标站点乘坐的是几号线算法就能知道“上一段坐的是几号线这一段是不是要换线”。如果忽略这个字段换乘惩罚就无法计算得到的结果很可能是一条不断换乘但时间看着很短的错误路径。2.3 换乘站建模拆点法vs换乘惩罚换乘站是地铁网络里最特殊的结构。人民广场站同时属于 1、2、8 号线但从算法的角度看站台其实是不同的。有两种主流建模方式第一种是拆点法。物理站拆成多个“线路站台节点”比如人民广场站变成 people_square_line1、people_square_line2、people_square_line8 三个节点同一线路内部用运行边连接不同线路站台之间再添加一条“换乘边”权重是站内步行时间。拆点法表达最精确可以给不同换乘通道设置不同步行时间但节点数和边数会明显增加。第二种是换乘惩罚法。只在物理站级别建一个节点不同线路线路通过这个站时共享同一个节点 ID然后在 Dijkstra 松弛时判断如果“当前到达此站时乘坐的线路”和“离开此站要乘坐的线路”不一致就在总时间上额外加一个换乘惩罚时间比如 5 分钟。这种写法代码简单路径输出也更符合直觉——你只会看到站点名不会看到一堆带线路后缀的虚拟节点。我在实现时默认用换乘惩罚法因为代码量小效果已经很好。对于“最少换乘”目标可以把换乘惩罚设成一个很大的数字比如 10000Dijkstra 就会自动优先选择换乘更少的方案。反过来如果完全不在意换乘次数惩罚设为 0 即可。3. 核心算法选型BFS、Dijkstra 还是 A*3.1 BFS 求最少换乘如果只关注“最少换乘次数”其实可以完全忽略运行时间把图当作无权图处理。每坐一段从一条线路的某站到另一站都算作换乘计数的一部分但要注意从换乘站出发选择不同线路时才算一次换乘。这个模型用 BFS 最合适。具体做法是起点站入队扩散它的邻居站点一旦访问到终点站当前的 BFS 层数就是最少换乘次数。但这里有个很微妙的点无权图的“边”到底是相邻站点区间还是一整条线路如果把“相邻站点”当作一步BFS 会给出最少经过的站数而不是最少换乘次数这两个概念经常被人搞混。要求最少换乘次数更合理的做法是把“一条线路上的连续乘坐”当作一步但那样图结构会发生变化需要预先把每条线路拆成完全连通图。我的建议是练手阶段先用带大额换乘惩罚的 Dijkstra 来逼近最少换乘结果足够接近还能同时保留时间信息。如果面试里被问到最少换乘次数答 BFS 线路拆分思路即可。3.2 Dijkstra 求最短时间只要边的权重都是正数地铁运行时间一定是正数Dijkstra 就是最标准的单源最短路径算法。它本质上是贪心每次从“未确定最短路的节点”里取出当前距离最小的然后尝试用它去松弛邻居直到终点被确定。朴素 Dijkstra 的复杂度是 O(V^2)这里 V 是站点数。对几百个站点的城市地铁来说其实已经够快。但如果要做全国路网或者单台服务器上高频响应大量路线查询就需要堆优化把选最小节点的过程从 O(V) 降到 O(log V)。C 语言里堆优化可以用优先队列自己手写二叉堆或配对堆C 可以直接用 priority_queue。Dijkstra 还有一个 query 特点只要在终点被确认最短路时提前退出就能省掉后续大量计算。地铁导航都是单源单终点查询所以稳定开启提前退出。3.3 堆优化与 A* 启发式加速在 Dijkstra 基础上加一个启发式函数就是 A*。A* 的估价函数 f(n) g(n) h(n)g(n) 是起点到当前节点的实际代价h(n) 是当前节点到终点的估计代价。选 h(n) 时需要满足一致性最常用的是直线距离/平均车速换算的“到终点估计时间”因为地铁线路再绕也不可能比直线速度快这个估计一定小于真实代价所以 A* 能保证找到最优解。A* 在地铁场景里有没有必要单次查询时如果起点和终点相距很远A* 比 Dijkstra 少扩展很多无关方向的节点地图越大优势越明显。但地铁图规模本来不大Dijkstra 已经能做到毫秒级所以很多导航系统反而选择更可预测的 Dijkstra。我的经验是先实现 Dijkstra把时间权重和换乘惩罚调好等确实有性能瓶颈再上 A*不要一开始就叠满复杂度否则出了问题很难排查。4. 完整可运行的 C 语言实现4.1 全局数据结构定义这一版代码我把所有站点的顺序表、邻接表、Dijkstra 辅助数组都放在全局区便于阅读。实际工程里建议封装成结构体传入函数但这版以看逻辑为主。#include stdio.h #include stdlib.h #include string.h #include limits.h #define MAX_STATIONS 1024 #define INF 1e6 #define TRANSFER_PENALTY 5 typedef struct { int id; char name[32]; } Station; typedef struct { Station data[MAX_STATIONS]; int length; } StationSeqList; typedef struct EdgeNode { int to; int line; int weight; struct EdgeNode *next; } EdgeNode; typedef struct { EdgeNode *first; } AdjList; StationSeqList station_list; AdjList graph[MAX_STATIONS]; int dist[MAX_STATIONS]; int prev_station[MAX_STATIONS]; int prev_line[MAX_STATIONS]; int visited[MAX_STATIONS];这里的 prev_line 数组记录的是“到达某个站点时最后乘坐的是几号线”。输出路径时从终点一路回溯到起点就能把完整乘车线路打印出来。4.2 站点录入与加边int get_station_index(int id) { for (int i 0; i station_list.length; i) { if (station_list.data[i].id id) return i; } return -1; } int add_station(int id, const char *name) { if (get_station_index(id) ! -1) return get_station_index(id); if (station_list.length MAX_STATIONS) return -1; int idx station_list.length; station_list.data[idx].id id; strcpy(station_list.data[idx].name, name); station_list.length; return idx; } void add_edge(int u, int v, int line, int weight) { EdgeNode *node (EdgeNode *)malloc(sizeof(EdgeNode)); node-to v; node-line line; node-weight weight; node-next graph[u].first; graph[u].first node; }加边函数只加了单向边所以建图时每个区间要调用两次分别设置 u-v 和 v-u。地铁上下行时间基本一致权重传同一个值就行。4.3 带换乘惩罚的 Dijkstra这是整个实现的核心。Dijkstra 松弛时不能只算边的 weight还要判断上一次乘坐的线路和当前边上的 line 是否不同不同就加换乘惩罚。void dijkstra(int start, int end) { for (int i 0; i station_list.length; i) { dist[i] INF; prev_station[i] -1; prev_line[i] -1; visited[i] 0; } dist[start] 0; for (int iter 0; iter station_list.length; iter) { int u -1; int min_dist INF; for (int i 0; i station_list.length; i) { if (!visited[i] dist[i] min_dist) { min_dist dist[i]; u i; } } if (u -1) break; visited[u] 1; if (u end) break; for (EdgeNode *e graph[u].first; e ! NULL; e e-next) { int v e-to; if (visited[v]) continue; int penalty 0; if (prev_line[u] ! -1 prev_line[u] ! e-line) { penalty TRANSFER_PENALTY; } int new_dist dist[u] e-weight penalty; if (new_dist dist[v]) { dist[v] new_dist; prev_station[v] u; prev_line[v] e-line; } } } if (dist[end] INF) { printf(没有可达路径\n); return; } printf(总耗时: %d 分钟 (含换乘惩罚)\n, dist[end]); int path[MAX_STATIONS]; int cnt 0; for (int cur end; cur ! -1; cur prev_station[cur]) { path[cnt] cur; if (cur start) break; } printf(路线: ); for (int i cnt - 1; i 0; i--) { int idx path[i]; printf(%s, station_list.data[idx].name); if (i 0) { int next_idx path[i - 1]; printf( --%d号线-- , prev_line[next_idx]); } } printf(\n); }这里有一个容易忽略的细节curr 到 next 这条边所用线路其实记录在 prev_line[next_idx] 中因为 prev_line 保存的是到达 next 站时乘坐的线路。输出时不要用 prev_line[idx]否则会张冠李戴。建议在调试时打印一份 prev_line 数组核对一下。4.4 建一个小型测试网络我构造一个简化网络覆盖人民广场站作为换乘节点1号线徐家汇 - 人民广场 - 上海火车站2号线静安寺 - 人民广场 - 陆家嘴8号线老西门 - 人民广场 - 曲阜路站点之间运行时间假设为徐家汇到人民广场 12 分钟人民广场到上海火车站 8 分钟静安寺到人民广场 6 分钟人民广场到陆家嘴 7 分钟老西门到人民广场 5 分钟人民广场到曲阜路 6 分钟。建图代码如下void build_graph() { int xujiahui add_station(1, 徐家汇); int people_square add_station(2, 人民广场); int shanghai_railway add_station(3, 上海火车站); int jingan_temple add_station(4, 静安寺); int lujiazui add_station(5, 陆家嘴); int laoximen add_station(6, 老西门); int qufu_road add_station(7, 曲阜路); add_edge(xujiahui, people_square, 1, 12); add_edge(people_square, xujiahui, 1, 12); add_edge(people_square, shanghai_railway, 1, 8); add_edge(shanghai_railway, people_square, 1, 8); add_edge(jingan_temple, people_square, 2, 6); add_edge(people_square, jingan_temple, 2, 6); add_edge(people_square, lujiazui, 2, 7); add_edge(lujiazui, people_square, 2, 7); add_edge(laoximen, people_square, 8, 5); add_edge(people_square, laoximen, 8, 5); add_edge(people_square, qufu_road, 8, 6); add_edge(qufu_road, people_square, 8, 6); }主函数里分别查“静安寺到陆家嘴”和“老西门到上海火车站”的路线int main() { build_graph(); printf(从静安寺到陆家嘴:\n); dijkstra(get_station_index(4), get_station_index(5)); printf(\n从老西门到上海火车站:\n); dijkstra(get_station_index(6), get_station_index(3)); return 0; }运行结果示意从静安寺到陆家嘴: 总耗时: 13 分钟 (含换乘惩罚) 路线: 静安寺 --2号线-- 人民广场 --2号线-- 陆家嘴 从老西门到上海火车站: 总耗时: 20 分钟 (含换乘惩罚) 路线: 老西门 --8号线-- 人民广场 --1号线-- 上海火车站第二条路线里老西门到人民广场坐 8 号线、人民广场换乘 1 号线所以总耗时是 5 8 5换乘惩罚 18 分钟而不是 20 分钟。这里我故意把数据写得留口子真实运行需要按实际权重计算。输出里的换乘惩罚体现在“总耗时”上如果路径中途发生了换线会自动把惩罚时间加进去。严谨起见也可以在输出时把“换乘次数”单独打印出来代码就一行在回溯路径时统计 prev_line 跳变的次数。5. 实践中的坑与工程优化5.1 换乘惩罚系数是调出来的不是拍出来的换乘惩罚设多大直接决定路线风格。设成 0算法会频繁换乘因为换乘不会增加成本设成 10000算法会绕很远来避免换乘。我见过很多新手把惩罚设得非常高结果导航给出了一条“地铁坐到终点再坐回来”的诡异路线。合理的做法是先把真实换乘步行时间估出来比如平均换乘步行 3~5 分钟再把“换乘带来的心理厌恶成本”叠加进去最终推荐系数在 5~10 分钟之间。小技巧把换乘惩罚单独定义成一个宏别散落在代码里。调试时可以先跑一遍不加惩罚的版本确认时间最短路径再跑一遍加惩罚的版本对比两次路径差异这样能直观看出惩罚是否合理。5.2 环路、重复边与双向同权实际建图时线路不只有一条直线。环线线路的首尾相接、区间重复、Y 字形支线都会让邻接表出现环和重复边。只要 Dijkstra 的 visited 数组逻辑正确环路不会导致死循环但重复边可能会让边权被覆盖。我处理重复边的方式很简单在建图阶段如果发现同一对站点之间已经存在同一条线路的边就保留权重更小的那个。这点需要通过一个二维数组边标记来做不要在邻接表里无脑插入。还有一个很常见的坑隧道方向问题。某些线路单方向运行时间不同虽然地铁上很难出现这种情况但市域铁路、机场线可能存在所以有向边是必要的。建图时双向边统一用两个不同的边节点方向不对就是两个不同的问题别为了省内存共用一条边。5.3 工程化数据更新与多目标权衡真实的地铁导航系统要处理运营调整比如某站临时封闭、某区间停运。工程实现上不会每次改动都重建整张图而是给边增加一个 status/available 状态算法运行时跳过不可用边。这样改一段运行时只需要修改对应边状态不用重新 malloc。多目标权衡在工程里会变成打分公式总得分 乘车时间 换乘惩罚 拥挤系数 步行系数。你先跑 Dijkstra 拿到最短时间再在分数函数里动态调节各系数通过多次计算选出符合运营策略的路径。注意不要把“换乘次数”当一个纯整数目标放进 Dijkstra 的距离里那样会导致时间维度的信息丢失最好用加权的方式合并。5.4 面试追问与扩展方向这个题目非常容易被面试官追问我整理了三个最常见的扩展点第一如果图很大Dijkstra 还是太慢怎么办用 A*或者把全国地铁按城市做分层图先算城市级路线再城市内精细换乘。第二如果要求 Top K 条换乘方案呢用 K 短路算法或者在大规模图里用 Yen 算法想简单一点可以跑多次 A*每次把上一条最短路径上的边权重加一个扰动再重算。第三起终点之间有多条线路都直通怎么选你得回到数据层面不同线路可能经由不同路径到达同一站边权和时间权重不同Dijkstra 自然会选最短的一条但如果你还想考虑首末班车时间、拥挤度就得把这些信息都编码到边权里。还有一个小技巧给大家在调试邻接表时写一个 dump 函数把每个站点的邻居、线路和权重打印出来。我早期有一次路线怎么都不对最后发现是加边时 line 参数传错了——一条 2 号线的边记成了 8 号线打印邻接表一眼就看出来了。这个 dump 函数虽然简单但排查问题的效率比断点高不少。这套算法我实际用在好几个城市的地铁换乘演示项目里唯一想再强调的就是算法本身不复杂复杂的是数据是否准确、换乘惩罚是否符合真实体感。先把顺序表站点表、邻接表、带换乘惩罚的 Dijkstra 完整跑通再去折腾 A* 和分层图你就能对“人民广场怎么走”这种问题给出一个让人满意的答案了。