Dijkstra算法是否总能返回最少边数路径？能否同时优化双目标？

结论 #

普通的Dijkstra算法无法直接保证在找到障碍代价最小的路径时，同时满足路径边数最少的要求，必须对算法的优先级判定规则做调整。

原因分析 #

普通Dijkstra仅以「障碍总数」作为唯一的优先级排序依据，当两条路径到达同一节点的障碍数相同，但边数不同时，算法可能先处理边数较多的那条路径。一旦该节点被标记为「已确定最短代价」，后续遇到的边数更少、障碍数相同的路径就会被直接跳过，最终得到的路径虽然障碍数是最小的，但边数并非最优。

举个简单例子：

• 路径1：S→A→T，障碍数1，边数2
• 路径2：S→B→C→T，障碍数1，边数3
  若普通Dijkstra的优先级队列先弹出路径2的节点T，就会直接把T的代价固定为障碍数1、边数3，后续路径1到达T时会被判定为「代价未更优」而忽略，最终得到的路径边数不是最少的。

解决方案 #

修改Dijkstra算法的优先级判定逻辑，使用复合优先级：

1. 优先比较路径的障碍总数，障碍数越少优先级越高；
2. 当两条路径的障碍数相同时，比较路径的边数，边数越少优先级越高。

把每个节点的代价存储为二元组(障碍数, 边数)，优先级队列按这个二元组升序排列（先比第一个元素，再比第二个）。这样算法的贪心策略会优先选择障碍数最少的路径，在障碍数相同的情况下，会优先选择边数更少的路径，最终就能得到同时满足两个目标的最优路径。

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