我将如何以最佳方式解决图论问题,其中边权重每隔一个甚至第三个跳变一次?我还能使用某种修改后的 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
现在根据第一跳是否加倍从源或其副本搜索,寻找到达目的地或其副本的最便宜路径。
关于algorithm - 边缘权重每隔一跳加倍的最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42191457/