带M次边权重减半折扣的有向图最短路径高效算法求解

核心思路 #

把传统Dijkstra算法的状态从「当前节点」扩展成**(当前节点, 已用折扣次数)**——因为M<10，每个节点最多有10种状态（0到M次折扣）。每个状态专门记录「到达该节点时，用了k次折扣后的最短距离」，精准追踪折扣使用情况，避免暴力递归的重复计算。

具体实现步骤 #

• 初始化距离数组：用dist[u][k]表示到达节点u且已用k次折扣的最短距离，初始时仅起点的dist[source][0] = 0，其余所有状态设为无穷大。
• 用小顶堆（优先队列）执行松弛操作，队列元素为(当前距离, 当前节点, 已用折扣次数)，初始入队(0, source, 0)。
• 每次取出堆中距离最小的状态，遍历当前节点的所有出边：
  1. 不使用折扣：计算新距离new_dist = 当前距离 + 边权，若该值小于dist[邻接节点][已用折扣次数]，则更新并将新状态加入队列。
  2. 使用折扣（已用次数<M时）：计算新距离new_dist = 当前距离 + 边权/2，若该值小于dist[邻接节点][已用折扣次数+1]，则更新并将新状态加入队列。
• 最终取目标节点所有dist[target][k]（k从0到M）中的最小值，即为最优路径长度。

为何比暴力递归高效 #

暴力递归会反复计算同一节点使用相同次数折扣的路径，存在大量冗余。而该方法通过状态记录，每个(节点, 折扣次数)状态仅处理一次，结合Dijkstra的贪心堆策略直接跳过非最优路径，时间复杂度为O((N*(M+1)) * log(N*(M+1)))，M<10的情况下，即使节点数N较大，也能高效运行。

注意事项 #

• 所有边权为正，Dijkstra的贪心逻辑完全适用，无需考虑负权边场景。
• 若题目要求整数结果，需提前明确边权减半后的取整规则（向下/向上取整）。

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