DAA-多段グラフ

多段グラフ G = (V, E) 頂点がに分割されている有向グラフです k (どこ k > 1)互いに素なサブセットの数 S = {s1,s2,…,sk}その結果、エッジ(U、V) Eであり、次いで、UЄS I及びVЄS 1 + 1パーティション内のいくつかのサブセットおよび|s1| = |sk| = 1。

頂点 s Є s1 と呼ばれます source と頂点 t Є sk と呼ばれる sink

G通常、加重グラフと見なされます。このグラフでは、エッジ(i、j)のコストはc(i、j)で表されます。したがって、ソースからのパスのコストs 沈む t このパスの各エッジのコストの合計です。

多段グラフの問題は、ソースから最小のコストでパスを見つけることです s 沈む t

多段グラフの概念を理解するために、次の例を検討してください。

式に従って、コストを計算する必要があります (i, j) 次の手順を使用します

ステップ-1:コスト(K-2、j)

このステップでは、3つのノード(ノード4、5、6)が次のように選択されます。 j。したがって、このステップで最小コストを選択するための3つのオプションがあります。

Cost(3、4)= min {c(4、7)+ Cost(7、9)、c(4、8)+ Cost(8、9)} = 7

Cost(3、5)= min {c(5、7)+ Cost(7、9)、c(5、8)+ Cost(8、9)} = 5

Cost(3、6)= min {c(6、7)+ Cost(7、9)、c(6、8)+ Cost(8、9)} = 5

ステップ2:コスト(K-3、j)

ステージk-3 = 2には2と3の2つのノードがあるため、2つのノードがjとして選択されます。したがって、値i = 2とj = 2と3です。

Cost(2、2)= min {c(2、4)+ Cost(4、8)+ Cost(8、9)、c(2、6)+

Cost(6、8)+ Cost(8、9)} = 8

Cost(2、3)= {c(3、4)+ Cost(4、8)+ Cost(8、9)、c(3、5)+ Cost(5、8)+ Cost(8、9)、 c(3、6)+コスト(6、8)+コスト(8、9)} = 10

ステップ-3:コスト(K-4、j)

コスト(1、1)= {c(1、2)+コスト(2、6)+コスト(6、8)+コスト(8、9)、c(1、3)+コスト(3、5)+ Cost(5、8)+ Cost(8、9))} = 12

c(1、3)+ Cost(3、6)+ Cost(6、8 + Cost(8、9))} = 13

したがって、最小コストのパスは次のようになります。 1→ 3→ 5→ 8→ 9