最短路モデル

概要

重み付きグラフの距離を計算し、距離の確定条件や最短路木の枝構造から経路・閉路の最適化を行う。

距離確定:非負重みを使う

緩和d[v]←min(d[v],d[u]+w)の式だけでは算法は決まらない。非負重みなら未確定頂点の最小距離を確定してよい。優先度付きキューのDijkstraはO((V+E) log V)。重みが0・1なら候補の距離が二層に限られ、0辺をdequeの前、1辺を後へ入れる0-1 BFSでO(V+E)。全辺1ならFIFOでよい。負辺のある元の式も、ポテンシャルで非負化できればこの原理へ戻せる。

依存順:経路集合を一段ずつ広げる

DAGではトポロジカル順が全先行状態の完了を保証し、重みが負でもO(V+E)でよい。ABC271 Eの辺列順では、処理済みprefixの辺をその順に選べる経路だけを表す。辺を自由に使う通常の最短路と混同せず、一つの辺出現を高々一度使う更新にする。

反復緩和:改善する閉路を検出する

Bellman–Fordでは高々k辺のwalkという不変量から、V−1回で十分な有限最短路と、V回目にも改善する到達可能な負閉路を区別する。O(VE)。最大路は符号反転して正閉路を調べる。始点から届く閉路でも、指定終点へ影響しなければその終点の答えは発散しない。

全点対:中継点集合のDP

Floyd–Warshallは中継点を{0,…,k−1}まで許す距離D_kを持ち、D_{k+1}[i][j]=min(D_k[i][j],D_k[i][k]+D_k[k][j])とする。kを最外ループにしてO(V³)、空間O(V²)。負辺は扱えるが負閉路のある組は有限距離と呼べない。ABC301 E・ABC338 Fでは距離計算は前処理であり、代表地点の訪問順と集合状態の設計が主題になる。

考え方

最短路の緩和式は共通でも、距離を確定する順は仮定で変わる。非負辺にはDijkstra、0・1辺にはdeque、DAGなら依存順、負辺があれば反復緩和の原理を使う。

初期化・更新・確定を分ける

単一始点ではd[s]=0、他は∞で初期化する。Dijkstraのheapには(0,s)を入れ、popした候補duが現在のd[u]と違えば古い候補として捨てる。一致する未確定uを確定し、全出辺を緩和して改善した頂点をheapへ入れる。真の最短pathで未確定集合へ最初に入る辺を見ると、その始点は既に確定し、その後の辺は全て非負なので、heapの最小候補より短い未確定距離は存在しない。これが確定の根拠であり、heap使用だけでは証明にならない。

0-1 BFSでは改善する0辺を前、1辺を後へ入れる。queue内の距離候補が現在最小dとd+1の二層になるため同じ確定順を保つ。単位辺BFSでは初回訪問で距離を確定し、各頂点を一度queueへ入れればよい。DAGはtopological順で各出辺を一度緩和する。指定辺列では旧d[u]から一回だけd[v]を更新し、処理前のpathにその辺出現を足す。u=vや同時更新を持つ一般の段では旧値を保存する。

Bellman–Fordの辺数不変量を厳密に使うなら、oldをコピーしたnextへ各辺について next[v]=min(next[v],old[u]+w) と更新して一段進める。段kは高々k辺のwalkとなる。V−1段後からV段目に改善する頂点を全て印し、元graphでそこから到達する頂点を伝播すれば、負閉路の影響範囲が分かる。有限最短walkはcycleを除いて高々V−1辺のpathにできるので、その範囲外の改善には負閉路が必要になる。

Floyd–Warshallは対角0、直接辺の最小重み、他∞から始め、kを外側、i,jを内側にして、両距離が有限のときだけ和で更新する。中継kを使わないpathと使うpathに分ける帰納法で正しい。D[k][k]<0のkについて、i→kとk→jが到達可能ならi→jの値は下に無限で、通常の有限距離として使わない。

根を通るcycleを最短路木から作る

無向非負重みgraphで根rからの最短路木を一つ取り、r以外の各頂点にroot pathの第一子labelを付ける。木辺を除いた辺uvでlabel[u]≠label[v]なら、二本のroot pathはr以外で交わらず、候補長d[u]+w(uv)+d[v]のcycleを作れる。r自身は別labelとし、非木辺rvも長さw(rv)+d[v]の候補にする。これにより多重なroot辺からなる二辺cycleも扱える。rの自己loopは別に候補へ加える。

任意のrを通るcycleをrootから両側へ見ると、木辺だけでcycleにはならず、どこかにこのlabel境界を越える非木辺がある。その両端の最短距離はcycle上の両側path長以下なので、対応候補の長さはcycle長以下。一方全候補は実際のcycleだから最小値は一致する。有向graphでは二root pathを逆に使えず、この方法をそのまま適用しない。

0-1 BFSのdequeにも候補距離を添え、取り出した候補が現在距離と違うか、既に確定した頂点なら捨てる。一致する未確定頂点の出辺を一度だけ展開する。古い候補を含めたdequeの候補距離は非減少で、その範囲は先頭距離とその+1以内なので、0辺を前・1辺を後に置く規則が距離順の確定を保つ。各辺が作る候補は高々一つであり、全deque操作と辺走査がO(V+E)になる。

成立条件と計算量

頂点のheap位置を管理するDijkstraはO((V+E) log(V+1))。上記の古い候補を残す実装はO((V+E) log(V+E+1))時間・O(V+E)空間となる。単純graphではlog(V+E+1)=O(log(V+1))だが、多重辺数が頂点数で界せない場合はheap候補数も数える。0-1 BFSとDAGはO(V+E)、Bellman–FordはO(VE)。全点対Floyd–WarshallはO(V³)。負閉路が始点から届き終点へ影響する場合、その終点の有限最短値はない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。重みと状態の定義を確認し、Dijkstraなどの標準的な最短路算法を使い分ける。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 重み付き最短路・経路復元・差分制約。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-weighted-shortest-path

最短路モデル

習得する技能

  • 許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。
  • 辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。
  • 根からの最短路木で第一枝の異なる頂点を結ぶ辺を列挙し、二本の木上経路と合わせて根を通る最小閉路を求められる。
  • 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。
  • DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 状態グラフのモデリングと探索。

このUnitを直接前提とする単元: difference constraints・不等式系の最短路化、最小費用流・circulation、平面graph双対・cut/path対応、最短路を証明する木・経路の復元、Steiner tree subset DP。

基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

このUnitでは扱わないもの

  • 最短路モデルの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠