algorithm - 边缘权重每隔一跳加倍的最短路径

Question

我将如何以最佳方式解决图论问题，其中边权重每隔一个甚至第三个跳变一次？我还能使用某种修改后的 Dijkstra 算法吗？

Answer 1

您可以构建一个新图来对不断变化的成本进行编码(尽管实际上，最好不要显式构建新图)。

给定一个图表

     1
  A --> B
  |   / |
2 |  /5 | 4
  v <   v
  C <-- D
     3

每个顶点产生两个顶点，每个弧产生两个弧。弧以原始权重从原始到副本，以双倍权重从副本到原始。

   1            5            3
A ---> B'    B ---> C'    D ---> C'

    2           10            6
A' ---> B    B' ---> C    D' ---> C

   2            4
A ---> C'    B ---> D'

    4            8
A' ---> C    B' ---> D

现在根据第一跳是否加倍从源或其副本搜索，寻找到达目的地或其副本的最便宜路径。