双准则最短路径算法Bug排查：步数优先+温度最优

问题背景 #

需要实现双准则最短路径算法：从节点0出发到节点n-1，优先保证路径步数最少，其次使最终温度（每步温度±1）尽可能接近0。输入格式为[n, m, 边列表]，边列表元素为[u, v, c]（u起点、v终点、c为±1），无有效路径时输出"ajajaj"。

当前代码通过了部分测试用例及70%的大规模输入，但存在两类Bug：

• 部分用例输出路径长于最短路径（如某测试用例输出(-2,4,[35,24,244,141])，正确输出应为(-1,3,[35,76,54])）
• 误判无有效路径

可能的算法逻辑问题 #

1. 最短路径优先级未严格保证 #

如果代码没有严格以步数最少为第一优先级，就会出现长路径覆盖短路径的情况：

• 误用深度优先搜索（DFS）而非广度优先搜索（BFS）：DFS可能先探索到长路径并记录，后续找到短路径时未更新覆盖
• 状态更新时未过滤步数更长的状态：当到达同一节点时，若当前步数大于该节点已记录的最短步数，仍继续处理该状态，导致生成更长路径

2. 状态定义不完整 #

每个状态必须绑定节点+当前步数，而非仅节点：

• 错误示例：仅记录每个节点的最优温度，未关联到达该节点的步数。这会导致：当以更长步数到达同一节点时，即使温度更优，也会覆盖短步数的状态，最终输出长路径
• 正确状态：应为(当前节点, 当前步数)，并为每个节点维护最短步数以及该步数下的**最优温度（最接近0）**和对应路径

3. BFS队列处理逻辑错误 #

BFS是保证最短步数的核心，若队列处理不符合规则：

• 未在发现节点已有更短步数时直接跳过当前状态：比如当前到达节点u的步数已经大于u的已记录最短步数，仍将该状态加入队列处理，浪费资源且可能生成错误路径
• 未优先处理步数相同的状态：同一层级（步数相同）的状态应全部处理完，再处理下一层级，避免短路径状态被延迟处理

4. 无路径判定条件错误 #

• 过早判定无路径：比如BFS未遍历完所有可能的最短路径节点，就认为无法到达目标节点n-1
• 未正确追踪节点可达性：目标节点的最短步数未被正确更新为有效值，导致误判为不可达

实现层面的常见坑 #

1. 初始化错误：
   • 节点0的初始步数应设为0，初始温度设为0（默认起点温度为0），其他节点的最短步数设为无穷大
2. 路径追踪错误：
   • 记录路径时未关联最短步数的状态，导致保存了长路径的节点序列
3. 温度最优判定错误：
   • 当两个路径步数相同时，未正确选择绝对值更小的温度；若温度绝对值相同，可任选其一（如优先正温度或负温度）
4. 重复状态过滤错误：
   • 到达同一节点且步数相同时，未保留温度更优的状态；或步数更长时未直接丢弃状态

调试建议 #

1. 打印中间状态：在BFS过程中，输出每个节点的已记录最短步数、对应最优温度和路径，检查目标节点n-1是否被短路径状态正确覆盖
2. 单步模拟测试用例：针对出错的测试用例，手动模拟BFS流程，对比代码每一步的状态更新是否符合预期
3. 严格状态更新逻辑：

   当到达节点u，当前步数为step，当前温度为temp，路径为path：
   - 如果step < u的已记录最短步数：
     更新u的最短步数为step，最优温度为temp，路径为path，将该状态加入队列
   - 如果step == u的已记录最短步数：
     如果abs(temp) < abs(u的已记录最优温度) （或abs相等时按需求选择）：
       更新u的最优温度为temp，路径为path
   - 如果step > u的已记录最短步数：
     直接跳过该状态，不处理
   

4. 修正无路径判定：仅当BFS队列遍历完毕，且目标节点n-1的最短步数仍为无穷大时，才输出"ajajaj"

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