边缘权重每隔一跳加倍的最短路径
Shortest Path with Edge Weight Doubled on Every Other Hop
我将如何以最佳方式解决图论问题，其中边权重每隔一个甚至第三个跳变一次？我还能使用某种修改过的 Dijkstra 算法吗？
您可以构建一个新图来对不断变化的成本进行编码（尽管实际上，最好不要显式构建新图）。
给定一个像
这样的图表
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
现在根据第一跳是否加倍从源或其副本搜索，寻找到目的地或其副本的最便宜路径。
我将如何以最佳方式解决图论问题，其中边权重每隔一个甚至第三个跳变一次？我还能使用某种修改过的 Dijkstra 算法吗？
您可以构建一个新图来对不断变化的成本进行编码（尽管实际上，最好不要显式构建新图）。
给定一个像
这样的图表 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
现在根据第一跳是否加倍从源或其副本搜索，寻找到目的地或其副本的最便宜路径。