最短路モデル
概要
重み付きグラフの距離を計算し、距離の確定条件や最短路木の枝構造から経路・閉路の最適化を行う。
距離確定:非負重みを使う
緩和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³)。負閉路が始点から届き終点へ影響する場合、その終点の有限最短値はない。
問題一覧
- ABC395 E「Flip Edge」 公式問題
- ABC325 E「Our clients, please wait a moment」 公式問題
- ABC286 E「Souvenir」 公式問題
- ABC463 E「Roads and Gates」 公式問題
- ABC277 E「Crystal Switches」 公式問題
- ABC237 E「Skiing」 公式問題
- ABC271 E「Subsequence Path」 公式問題
- ABC213 E「Stronger Takahashi」 公式問題
- ABC431 E「Reflection on Grid」 公式問題
- ABC246 E「Bishop 2」 公式問題
- ABC291 F「Teleporter and Closed off」 公式問題
- ABC416 E「Development」 公式問題
- ABC342 E「Last Train」 公式問題
- ABC243 E「Edge Deletion」 公式問題
技能・出典
主題: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。既習技能: 基準witnessから変更影響を局所化する(基準となる解や経路を証拠に、答えが変わり得る変更だけを特定して再計算を局所化できる。)。主タグ: 最短路モデル / 補助タグ: 基準解による変更影響の局所化
- ABC257 F「Teleporter Setting」 公式問題
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 最短路モデル / 補助タグ: 有界全列挙・有限case分解
- ABC307 F「Virus 2」 公式問題
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最短路モデル / 補助タグ: 単調進行による償却解析、priority queue・best-first列挙
- ABC245 G「Foreign Friends」 公式問題
- ABC232 G「Modulo Shortest Path」 公式問題
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。)。主タグ: 最短路モデル / 補助タグ: 座標・値の順序保存圧縮
- ABC308 Ex「Make Q」 公式問題組合せ: 最短路を証明する木・経路の復元
技能・出典
主題: 最短路モデル(根からの最短路木で第一枝の異なる頂点を結ぶ辺を列挙し、二本の木上経路と合わせて根を通る最小閉路を求められる。)。既習技能: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。主タグ: 最短路モデル / 補助タグ: 最短路を証明する木・経路の復元
- ABC414 G「AtCoder Express 4」 公式問題
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: Segment Treeのcanonical区間分解(区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。)。主タグ: 最短路モデル / 補助タグ: Segment Treeのcanonical区間分解
- ABC243 Ex「Builder Takahashi (Enhanced version)」 公式問題組合せ: 幾何の基本判定と座標変換
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 最短路モデル / 補助タグ: 幾何の基本判定・配置・座標変換
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC218 F「Blocked Roads」 公式問題
技能・出典
主題: 基準witnessから変更影響を局所化する(基準となる解や経路を証拠に、答えが変わり得る変更だけを特定して再計算を局所化できる。)。追加で学ぶ技能: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 最短路を証明する木・経路の復元、基準解による変更影響の局所化 / 補助タグ: 最短路モデル
- ABC250 Ex「Trespassing Takahashi」 公式問題
技能・出典
主題: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。追加で学ぶ技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC252 E「Road Reduction」 公式問題主題: 最短路を証明する木・経路の復元
技能・出典
主題: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 最短路を証明する木・経路の復元 / 補助タグ: 最短路モデル
- ABC261 G「Replace」 公式問題主題: 区間合成・領域分割DP
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 最短路モデル
- ABC264 G「String Fair」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: 最短路モデル(辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。)。主タグ: 有限状態automatonの構成、最短路モデル
- ABC297 E「Kth Takoyaki Set」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 最短路モデル
- ABC299 E「Nearest Black Vertex」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 構成解・witness復元 / 補助タグ: 最短路モデル
- ABC301 E「Pac-Takahashi」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。 BFSで重要地点間の距離を前計算し、移動の全履歴を距離へ圧縮する。その上でdp[S][v]から未訪問の代表地点へ進む部分集合DPを学び、最後に出口への距離を加えて時間制約を判定する。通過した菓子を全て状態に記録しなくても最適値を失わない理由も確かめる。主タグ: 部分集合・bitmask状態DP / 補助タグ: 最短路モデル
- ABC305 E「Art Gallery on Graph」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 最短路モデル
- ABC338 F「Negative Traveling Salesman」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。 Floyd–Warshallで全点対距離を前計算し、最短路閉包上の訪問順を部分集合DPで学ぶ。maskは代表として訪問順へ追加した頂点集合であり、距離前計算の途中で通る頂点を禁止しない。任意のwalkから初訪問順を取り出す方向と、DP解をwalkへ展開する方向で同値性を示す。主タグ: 部分集合・bitmask状態DP / 補助タグ: 最短路モデル
- ABC364 G「Last Major City」 公式問題
技能・出典
主題: Steiner tree subset DP(terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: Steiner tree subset DP / 補助タグ: 最短路モデル
- ABC369 E「Sightseeing Tour」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: 最短路モデル
- ABC375 F「Road Blocked」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。主タグ: 逆向きのオフライン処理 / 補助タグ: 最短路モデル
- ABC375 G「Road Blocked 2」 公式問題
技能・出典
主題: lowlinkで橋・関節点を特定する(DFS木の到達時刻とlowlink値を計算し、橋と関節点の判定条件を説明できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。 両端からのDijkstraで距離を前計算し、d_s[u]+w(u,v)+d_t[v]=d_s[t]を満たす辺だけで最短路部分グラフを作る。そのグラフでlowlinkによる橋判定を学び、橋と全最短路に不可欠な辺を対応させる。元グラフの橋判定とは違う。正重みによる距離の増加を使って対応を証明する。主タグ: lowlinkによる橋・関節点の検出 / 補助タグ: 最短路モデル
- ABC393 G「Unevenness」 公式問題
技能・出典
主題: Lagrangian relaxation・Aliens trick(個数制約へpenalty λを加えたoracleで双対下界を求める。厳密復元には個数別最適値の離散凸性などから対象個数で双対ギャップがないことを証明し、その上で個数単調性とtie-breakにより支持直線を探索する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 連分数・Stern–Brocotで有理近似する(Euclid互除法・連分数・Stern–Brocotの区間を使い、分母上限下の最良有理近似を求められる。) / 最短路モデル(辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。) / 最小費用流・circulation(流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: 最小費用流・circulation、連分数・Stern–Brocot有理近似、最短路モデル
- ABC395 G「Minimum Steiner Tree 2」 公式問題
技能・出典
主題: Steiner tree subset DP(terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: Steiner tree subset DP / 補助タグ: 最短路モデル
- ABC429 F「Shortest Path Query」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 半環行列・min-plus/max-min遷移(遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。) / 最短路モデル(DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。)。主タグ: 区間monoid要約 / 補助タグ: 半環行列・min-plus/max-min遷移、最短路モデル
前提・学習成果・出典
習得対象の目安: 緑色(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では扱わないもの
- 最短路モデルの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。