shortest_path.html

<title>最短路問題</title>
<h4 class="shadow">最短路問題</h4>
<p>
グラフ上で最小の重みをもつパスを答える問題。
入力のグラフには重みが負の閉路は存在しないと仮定する。
</p>
<h3>単一始点最短路問題 (single-source shortest path)</h3>
<p>
ある始点から全ての頂点への<b>ある最短路</b>を考えると、有向木の構造を成し、最短路木と呼ばれる。
また、ある始点から全ての頂点への<b>全ての</b>最短路も、重みが正の場合にはDAGによって表現することができる。
</p>
<p>
ダイクストラ法を用いると$O(V^2)$時間または$O(E \log V)$時間、理論的には$O(E + V \log V)$で解くことができる。
ただし、単純には辺の重みが非負の場合にのみ適用できる。
</p><p>
重みが整数でかつ最短路の距離がある定数$W$で抑えられる場合、ダイクストラ法を適切に実装することで$O(E + W)$時間で解ける。
重みが整数の場合、理論的には一般の場合よりも速い計算量で解くことができる。
</p><p>
ベルマンフォード法を用いると$O(V E)$時間で解くことができる。
これは重みが負の辺があっても適用することができる。
適切に実装することで負閉路を検出することもできる。
ベルマンフォード法のある実装「queue-based Bellman-ford」は経験的にはより高速に実行できる。
</p>
<h3>全点対最短路問題 (all-pair shortest path)</h3>
<p>
ワーシャルフロイド法を用いると$O(V^3)$時間で解くことができる。
</p>
<h3>線形計画法表現とその双対問題</h3>
<p>
競技プログラミングにおいてはよく問題が出される。
(だれか書いて)
</p>
<h3>その他</h3>
<p>
グラフを陽に持たないで実行することも多い。
</p>
<p>
DAGにおいてはDPをすることで線形時間で解くことができる。
</p>
<p>
頂点に重みがついている場合、その頂点に隣接する辺に重みを足すことで問題を還元できる。
</p>
<p>
転置グラフ上で単一始点最短路を求めることで"単一終点複数始点"の最短路を一度に求められる。
</p>
<p>
分割統治法を用いることで幅が小さいグラフ上で最短路クエリに答えたりできる。(UTPC 最短路クエリ)
</p>