重み付き最短路・経路復元・差分制約

概要

辺重みに応じた距離計算、距離等式による経路復元、差の不等式を緩和へ写す制約系への応用を順に学ぶ。

考え方

距離値は上界だけでは最短性を証明できない。各辺でd[v]≤d[u]+wとなる下界の条件と、実際に同じ長さの経路があることを合わせると最短距離の証拠になる。

成立条件と計算量

距離と前駆辺の検査はO(V+E)。到達不能頂点を有限距離と混ぜず、ゼロ重み辺で前駆関係がcycleにならないようにする。証拠を保持するとqueryや局所変更の影響を議論しやすくなる。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

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

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。辺の重みに合う距離計算を選び、最短路の復元へ進む入口。

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

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

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

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 辺重みや最短距離を扱わず、到達可否だけを求める探索、および最短路に限らない一般の変更影響解析。

根拠