他のホップごとに2倍のエッジウェイトを持つ最短パス

Question

エッジウェイトが1つおきに、あるいは3ホップでも変化するグラフ理論問題を、どうやって最適に解決できますか？私はまだ何種類かの修正されたDijkstraのアルゴリズムを使用できますか？

Answer 1

変化するコストを符号化する新しいグラフを作成することができます（実際には、新しいグラフを明示的に作成しない方が良いでしょう）。

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

ようなグラフが与えられると、各頂点は、2つの頂点を生じさせ、各アークは、2つの円弧を生じさせます。アークは元の重量から元の重量にコピーされ、コピーから元の重さの重量になります。今

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 

宛先またはそのコピーへの安い経路を探し、ソースまたは最初のホップが2倍にされているかどうかに応じて、そのコピーのいずれかから検索します。