Design-and-analysis-of-algorithms-multistage-graph
DAA-多段グラフ
多段グラフ* G =（V、E）は、頂点が *k （ k> 1 ）個の互いに素なサブセットに分割されている有向グラフです S = \ {s〜1〜、s〜2〜 、…、s〜k〜} _ エッジ（u、v）がEにある場合、パーティション内の一部のサブセットに対して_uЄs〜i〜_および_v s s〜1 + 1〜 * _ s〜1〜' | = | ' s〜k〜_ * | = 1。
頂点 sЄs〜1〜 は source と呼ばれ、頂点 tЄs〜k〜 は 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）
Cost（1、1）= \ {c（1、2）+ Cost（2、6）+ Cost（6、8）+ Cost（8、9）、c（1、3）+ Cost（3、5） +コスト（5、8）+コスト（8、9））} = 12
c（1、3）+コスト（3、6）+コスト（6、8 +コスト（8、9））} = 13
したがって、最小コストのパスは 1→3→5→8→9 です。
