边缘权重加倍的最短路径每个其他跳

我该如何最优地解决一个图论问题，其中边缘权重每隔一个甚至第三跳变化？我仍然可以使用某种改进的Dijkstra算法吗？边缘权重加倍的最短路径每个其他跳

2017-02-12 Sauhaarda

您可以构建一个新图来编码不断变化的成本（尽管实际上，最好不要明确构建新图）。

给定图像

 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

现在从源或其根据第一跳是否加倍复制搜索，寻找到目的地或者其复印件最廉价的路径。

来源

2017-02-12 19:07:29

这是否只适用于其他边缘重量翻倍？或者是否可以修改它，并将其应用于每一跳都翻倍的？例如每第三跳或第四跳？你会通过在顶部添加另一个图表来完成这项工作吗我认为这是有道理的。非常感谢！ – Sauhaarda

@Sauhaarda总的想法是，给定一个图（V，A），其中每个第k跳应该加倍，构造一个新的图形，顶点V x {0，...，k- 1}和弧{（v，j ） - >（w，（j + 1）mod k）| （v，j） - >（w，（j + 1）mod k）的权重是2的权重（在A中为j，并且在{0，...，k- v，w）如果j = <你想要的>否则1x。 –

我为你的帖子+1了，但因为我的名声很少，所以没有任何效果。 – Sauhaarda

边缘权重加倍的最短路径每个其他跳

回答

相关问题