如何在最短路径算法中为特定类型边按累计路径长度附加额外成本

核心调整：扩展Dijkstra算法的状态维度 #

Dijkstra本身支持这类和路径前序累计值相关的动态成本计算，你只需要修改原算法的状态定义即可，不需要更换算法框架。
原Dijkstra的状态仅记录(当前总成本, 当前节点)，无法追踪特定类型边的累计距离，我们将状态扩展为(当前总成本, 当前节点, 特定类型边累计距离模100的余数)即可解决问题。

具体执行逻辑 #

• 状态初始化：起点的初始状态为(0, 起点ID, 0)，即初始成本为0，特定类型边累计距离余数为0
• 非目标类型边转移：如果当前走的边不是你要统计的特定类型，总成本直接叠加该边原有权重，余数保持当前值不变，因为这类边的距离不计入累计规则
• 目标类型边转移：假设当前状态的余数为r，当前要走的目标类型边距离为d，单满100单位的额外成本为fee：
  1. 计算本次触发的额外成本次数：add_times = (r + d) // 100
  2. 新增总成本 = 边原有权重 + add_times * fee
  3. 新的余数 = (r + d) % 100
• 状态剪枝：对于同一个节点+同一个余数的组合，仅保留记录过的最低总成本，若新到达该状态的成本高于已有记录，直接跳过该状态的后续拓展

方案优势 #

• 完全符合满100整数倍才追加成本的规则，无平摊法的边界误差
• 性能损耗极低：模100的余数只有0-99共100种可能，属于固定常数，算法时间复杂度仅为原来的常数倍，实际运行几乎无感知
• 适配性强：如果后续需要调整累计阈值（比如改为满200追加成本），仅需要修改模数为对应阈值即可，核心逻辑无需改动

注意：只要你的额外成本为非负值，整个状态转移的成本仍然满足非负要求，Dijkstra算法可正常运行，不需要更换为其他最短路径算法。

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