基于Dijkstra的公交路径规划：双成本下的多项式算法选型

针对你提到的时间+票价双成本公交路径问题，直接用DFS效率太低，这里给出一套多项式时间的优化方案，完全契合你提到的约束条件：

第一步：先做时间范围预筛选 #

既然只需要准时到达目的地（比如赶上班），先把所有不可能在截止时间前到终点的班次砍掉，大幅减少后续计算量：

• 先算出每个站点到目的地的最短行驶时间：因为相邻站行驶时间固定，统计每个站点到终点的最少站数，乘以单站时间得到min_time_to_dest[station]
• 设目的地最晚到达时间为T_deadline，对每个班次的发车时间t_depart，只要t_depart + min_time_to_dest[当前站点] > T_deadline，直接丢弃这个班次

第二步：构建精准的状态图 #

把「站点+到达时间」作为图的核心节点，这样能同时追踪时间和票价状态：

• 节点：(站点ID, 到达时间)，代表在该时间点抵达这个站点
• 边分两类：
  • 换乘边：如果在站点S的到达时间是t1，同一站点有另一班次发车时间t2 ≥ t1，则加一条从(S, t1)到(S, t2)的边，票价成本+0，时间增加t2-t1
  • 行驶边：某线路从站点S发车时间t_depart，经过m个站到站点E，到达时间是t_depart + m×单站时间，加一条从(S, t_depart)到(E, 到达时间)的边，票价成本+该线路固定票价，时间增加m×单站时间

第三步：用改进版Dijkstra算法求解 #

这是核心，我们要找的是「不超过截止时间的前提下，票价最低的路径」，所以对Dijkstra做针对性调整：

• 维护一个状态数组best[站点][到达时间]，记录抵达该状态的最小累计票价；如果后续出现同一站点的状态，时间更晚且票价更高，直接跳过
• 用小顶堆作为优先级队列，优先弹出票价更低的状态；票价相同时，优先弹出到达时间更早的状态，这样能更快锁定符合要求的最优解
• 终止条件：当弹出的状态是目的地且到达时间≤T_deadline，此时的累计票价就是最优解；如果队列空了，说明没有符合条件的路径

时间复杂度验证 #

假设筛选后剩余班次为k'（≤原k），站点数p：

• 节点总数最多是p×k'，每个站点对应筛选后的班次到达时间
• 边数：换乘边通过排序优化后，每个站点最多k'条有效边；行驶边数量等于筛选后的班次对应的站段数，整体是O(p×k' + k')量级
• 算法整体时间复杂度为O((p×k')×log(p×k'))，属于关于线路数n、原实例数k、站点数p的多项式时间，完全满足你的要求

额外优化点 #

• 每个站点的所有到达/发车时间提前排序，处理换乘时只需要按顺序匹配，避免生成大量无效换乘边
• 同一站点的状态中，如果存在t1 ≤ t2且票价cost1 ≤ cost2，直接丢弃t2对应的状态——它在时间和成本上都没有任何优势，没必要保留

内容的提问来源于stack exchange，提问作者Karen Azuma