无向加权图从A出发遍历B、C、E的最短路径及基于堆的Dijkstra算法修改

你遇到的不是常规单源到单终点的最短路径问题，属于起点固定、无指定终点、要求覆盖固定必访节点集的最短路径问题，因为必访节点只有B、C、E三个，规模极小，完全可以在现有堆优化Dijkstra的基础上低成本改造，不需要引入复杂的TSP动态规划框架。

不需要推翻原有堆的实现逻辑，仅需对状态存储和终止条件做小范围调整即可：

• 改造状态维度：原来Dijkstra的堆中仅存储(累计距离, 当前所在节点)二元组，现在替换为三元组(累计距离, 当前所在节点, 已访问必访节点的位掩码)。因为仅需追踪B、C、E三个点的访问状态，3个二进制位就能覆盖所有可能的状态组合（比如二进制001代表访问过B、010代表访问过C、100代表访问过E、111代表三个点全部访问完成），计算成本极低。

  位掩码的标记逻辑非常简单：给B、C、E分别分配一个二进制位的索引，标记已访问节点时用位运算更新即可，例如给B分配0位、C分配1位、E分配2位，标记已访问的代码逻辑为mask |= (1 << index)；判断是否覆盖全部必访节点时，直接判断if mask == 0b111即可终止。

• 改造距离记录逻辑：原来的距离数组仅以当前节点为键记录最短距离，现在改为以(当前节点, 已访问位掩码)为键记录到对应状态的最短累计距离，逻辑和原来完全一致——如果新计算的累计距离小于同键的已记录值，就将新状态推入堆中。
• 改造终止条件：原来的Dijkstra是到达指定终点就停止，现在只要从堆中弹出的状态满足「已访问位掩码等于111（即覆盖所有必访节点）」，该状态对应的累计距离就是全局最短值，直接返回即可，不需要继续扩展后续路径。

如果你不想改动原有状态维度，也可以用预计算的简化方案：因为顶点总量极少，只需要以A、B、C、E四个和访问流程相关的点为源点，各跑一次原有堆优化Dijkstra，算出任意两点之间的最短通行距离，再枚举从A出发、顺序覆盖B/C/E的所有3!=6种排列，累加每种排列的相邻点最短距离，取总距离最小的结果即可，计算量可以忽略不计。

先预计算所有相关点对的最短距离（基于给定边权，所有边权为正，Dijkstra计算结果准确）：

• A到B最短5（直连边）
• A到C最短6（直连或走A-D-C）
• A到E最短4（直连边）
• B到C最短4（直连边）
• B到E最短6（直连边）
• C到E最短5（直连边）

枚举所有可能的访问顺序后，总路程最短的方案为：A -> E -> C -> B

• 累计路程：A到E(4) + E到C(5) + C到B(4) = 13
• 访问覆盖：依次经过E、C、B三个必访节点，终点无强制要求，符合需求
• 对比其他方案：比如A->B->C->E总路程14、A->E->B->C总路程14，均长于上述方案。

• 不需要额外禁止节点重复访问：因为所有边权都是正的，Dijkstra的贪心逻辑天然会排除无意义的绕路循环，即使路径中重复经过非必访节点（比如D）也不会得到更差的结果。
• 不要强制指定终点：无指定终点的前提下，只要必访节点全部覆盖就可以终止算法，不需要额外走到某个固定点。

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