最短路問題の最適性条件と reduced arc length

最短路問題

有向グラフが与えられたとき，始点 $s$ から各頂点への最短路を求める問題を単一始点最短路問題といいます．
この記事では，最短路問題の最適性条件と reduced arc length の性質を使ったアルゴリズムを紹介します．
以下では，頂点数を $n$，辺数を $m$，各辺 $(u, v)$ のコストを $c_{uv}$ で表します．また，グラフは負閉路がなく始点 $s$ からすべての頂点に到達可能であることを仮定します．

最短路問題の最適性条件

頂点集合を $N$，辺集合を $A$，辺を $(u, v)$ とします．始点 $s$ から各頂点 $v$ への最短距離の上界を $d_v$ で表し，これを距離ラベルと呼びます．特に，$d_s = 0$ です．
各頂点 $v \in N$ について，$d_v$ が始点 $s$ から頂点 $v$ への最短距離であるための必要十分条件は以下が成り立つことです．

$$ \begin{equation} d_v \le d_u + c_{uv} \quad \forall (u, v) \in A \end{equation} $$

証明

まず，必要条件であることを示します．
$d$ が最短距離を表しているとします．任意の辺 $(u,v)$ について，頂点 $u$ への最短路のあとに辺 $(u,v)$ を通ることで，コスト $d_u+c_{uv}$ の頂点 $v$ への経路が得られます． $d_v$ は頂点 $v$ への最短距離なので，

$$ d_v \le d_u+c_{uv} $$

が成り立ちます．

次に，十分条件であることを示します．
頂点 $s$ から頂点 $v$ への任意の有向パス $P$ が $s = i_1 \rightarrow i_2 \rightarrow \cdots \rightarrow i_{k-1} \rightarrow i_k = v$ であったとします．
不等式 (1) から以下の式がそれぞれ成り立ちます．

$$ \begin{aligned} d_v =\; & d_{i_k} && \le\; d_{i_{k - 1}} && +\; c_{i_{k - 1}i_{k}}, \\ & d_{i_{k - 1}} && \le\; d_{i_{k - 2}} && +\; c_{i_{k - 2} i_{k - 1}}, \\ & \vdots \\ & d_{i_{2}} && \le\; d_{i_{1}} && +\; c_{i_{1}i_{2}} = c_{i_{1}i_{2}}. \end{aligned} $$

式をそれぞれ代入すると

$$ d_v = d_{i_{k}} \le c_{i_{k-1}i_{k}} + c_{i_{k-2}i_{k-1}} + \dots + c_{i_{1}i_{2}} = \sum_{(u, v) \in P} c_{uv} $$

となり，$d_v$ は始点 $s$ から頂点 $v$ への任意の有向パスのコスト以下です．
したがって，$d_v$ は始点 $s$ から頂点 $v$ への最短距離の下界です．
一方，距離ラベルの定義から $d_v$ は最短距離の上界でもあるため，$d_v$ は最短距離に一致します．

以上のことから，「各頂点 $v \in N$ について距離ラベル $d_v$ が最短路の長さである」の必要十分条件は，「各辺 $(u, v) \in A$ について $d_v \le d_u + c_{uv}$ を満たす」であることがわかりました．

reduced arc length の性質

各頂点のポテンシャル $\pi$ が与えられたとき，

$$ c_{uv}^{\pi} = c_{uv} + \pi_u - \pi_v $$

を reduced arc length と呼びます．
reduced arc length には次の性質があります．

任意の閉路 $W$ について，$\sum_{(u, v) \in W} c_{uv}^{\pi} = \sum_{(u, v) \in W} c_{uv}$
頂点 $k$ から頂点 $l$ への任意の有向パス $P$ について，$\sum_{(u, v) \in P} c_{uv}^{\pi} = \sum_{(u, v) \in P} c_{uv} + \pi_k - \pi_l$
$\pi$ が最適な距離ラベルならば，すべての辺 $(u, v)$ について $c_{uv}^{\pi} \ge 0$ が成り立つ

性質 1 の証明

$$ \begin{aligned} \sum_{(u, v) \in W} c_{uv}^{\pi} &= \sum_{(u, v) \in W} (c_{uv} + \pi_u - \pi_v) \\ &= \sum_{(u, v) \in W} c_{uv} + \sum_{(u, v) \in W} (\pi_u - \pi_v) \\ &= \sum_{(u, v) \in W} c_{uv} \\ \end{aligned} $$

任意の有向閉路 $W$ において，頂点 $u$ は $+\pi_u$としてちょうど $1$ 回，$-\pi_u$ としてちょうど $1$ 回出現するため，$\sum_{(u, v) \in W} (\pi_u - \pi_v)$ の項は $0$ となります．

性質 2 の証明

$$ \begin{aligned} \sum_{(u, v) \in P} c_{uv}^{\pi} &= \sum_{(u, v) \in P} (c_{uv} + \pi_u - \pi_v) \\ &= \sum_{(u, v) \in P} c_{uv} + \sum_{(u, v) \in P} (\pi_u - \pi_v) \\ &= \sum_{(u, v) \in P} c_{uv} + \pi_k - \pi_l \\ \end{aligned} $$

頂点 $k$ と頂点 $l$ 以外の頂点は，$+\pi_u$ としてちょうど $1$ 回，$-\pi_u$ としてちょうど $1$ 回出現するため互いに打ち消し合います．
頂点 $k$ は $+\pi_k$ として，頂点 $l$ は $-\pi_l$ としてちょうど $1$ 回出現します．

したがって，頂点 $k$ から頂点 $l$ へのどのような有向パスについても，変換前後のコストの差は一定値 $\pi_k - \pi_l$ です．

性質 3 の証明

最適性条件から直ちに言えます．

次節からは，reduced arc length の性質を使ったアルゴリズムと問題を見ていきます．

Johnson’s algorithm

任意の $2$ 頂点の組 $(u, v)$ に対して頂点 $u$ から頂点 $v$ への最短路を求める問題を全点対最短路問題と呼びます．
Johnson’s algorithm は全点対最短路問題を解くアルゴリズムです．

頂点数が $n$ のとき，単一始点最短路問題を $n$ 回解くことによって全点対最短路を求めることができます．ただし，グラフにコストが負の辺があると，単一始点最短路問題を解くのに Dijkstra 法を使うことができません．

そこで，グラフのコストを reduced arc length に変換したグラフ上で最短路を求めることにします．reduced arc length の性質 3 から，最適な距離ラベル $\pi$ に対する reduced arc length のコストはすべて 0 以上であるため Dijkstra 法を使うことができます．

変換したグラフ上で最短距離を求めたあと，性質 2 を使って元のグラフの距離に変換します．始点と終点を固定したとき，reduced arc length への変換によってすべてのパスに同じ定数が加わるため，最短路となるパス自体は変わりません．

最適な距離ラベルは Bellman-Ford 法を使い求めることができます．もし負閉路が見つかった場合はアルゴリズムを終了します．

計算量

Dijkstra 法に二分ヒープを使うとします．Bellman-Ford 法に $O(nm)$，Dijkstra 法に $O((n + m) \log n)$ かかるため，計算量は全体として $O(nm + n ((n + m) \log n))$ となります．

AOJ - All Pairs Shortest Path

例として，AOJ - All Pairs Shortest Path を解きます．
すべての頂点を始点から到達可能にするため，人工頂点 $s$ を追加し，$s$ から他のすべての頂点にコスト $0$ の辺を張ります．
この $s$ を始点として Bellman-Ford 法を使うことで最適な距離ラベルを求めることができます．実装では人工頂点を追加するのではなく，Bellman-Ford 法の距離ラベルの初期値をすべて $0$ とすることで対応しています．
提出コード

ABC237 E - Skiing

reduced arc length を使った問題を紹介します．

問題概要
$N$ 個の広場とそれらを結ぶ $M$ 本の坂，各広場 $u$ の高さ $H(u)$ が与えられる．広場 $1$ から楽しさ $0$ で出発する．高さ $H(u)$ の広場 $u$ から高さ $H(v)$ の広場 $v$ へ移動するとき，

$H(u) \ge H(v)$ なら，楽しさが $H(u)-H(v)$ 増える
$H(u) < H(v)$ なら，楽しさが $2(H(v)-H(u))$ 減る

とする．広場 $1$ から坂を好きな回数だけ移動したときに得られる楽しさの最大値を求めよ．

各坂を両方向の $2$ 本の有向辺として表します．各有向辺のコストを，その辺を移動したときの楽しさの変化の符号を反転したものとします．
つまり，$H(u) \ge H(v)$ のとき，頂点 $u$ から頂点 $v$ への辺のコストは $H(v)-H(u)$，頂点 $v$ から頂点 $u$ への辺のコストは $2(H(u)-H(v))$ です．
このグラフ上で，頂点 $1$ から他の頂点への最短距離を求めます．

このグラフには負のコストの辺があるため，Bellman-Ford 法を使えば最小コストを求めることができますが，有向辺数は $2M$ なので計算量は $O(NM)$ となり，TLE になってしまいます．
そこで，グラフのコストを reduced arc length に変換したグラフ上で最短路を求めることにします．
各頂点のポテンシャル $\pi$ を考えます．$H(u) \ge H(v)$ のとき，$c_{uv}^{\pi}$ と $c_{vu}^{\pi}$ は以下のように表せます．

$$ \begin{aligned} c_{uv}^{\pi} &= c_{uv} + \pi_u - \pi_v = H(v) - H(u) + \pi_u - \pi_v \\ c_{vu}^{\pi} &= c_{vu} + \pi_v - \pi_u = 2(H(u)- H(v)) + \pi_v - \pi_u \\ \end{aligned} $$

$u$ と $v$ についてまとめて式を整理します．

$$ \begin{aligned} c_{uv}^{\pi} &= (H(v) - \pi_v) - (H(u) - \pi_u) \\ c_{vu}^{\pi} &= (2H(u) - \pi_u) - (2H(v) - \pi_v) \\ \end{aligned} $$

$c_{uv}^{\pi} \ge 0$ かつ $c_{vu}^{\pi} \ge 0$ となるように，各頂点 $u$ について $\pi_u = H(u)$ とすると以下のようになります．

$$ \begin{aligned} c_{uv}^{\pi} &= (H(v) - H(v)) - (H(u) - H(u)) = 0 \\ c_{vu}^{\pi} &= (2H(u) - H(u)) - (2H(v) - H(v)) = H(u) - H(v)\\ \end{aligned} $$

以上のことから，$H(u) \ge H(v)$ のとき，辺のコストは次のように定めることができます．

辺 $(u, v)$ のコスト：$0$
辺 $(v, u)$ のコスト：$H(u) - H(v)$

すべての辺のコストは $0$ 以上なので，このグラフ上で Dijkstra 法を使い，頂点 $1$ から各頂点 $u$ への最短距離を求めることができます．
ここで求めた値は reduced arc length での値であるため，元のグラフ上の距離に戻す必要があります．

変換後のグラフで頂点 $1$ から頂点 $u$ への最短距離を $\operatorname{dist}'(u)$ とすると，元のグラフでの最短距離は

$$ \operatorname{dist}'(u) - H(1) + H(u) $$

です．また，元のグラフの辺のコストは楽しさの変化の符号を反転したものなので，頂点 $u$ まで移動したときの楽しさの最大値は

$$ H(1) - H(u) - \operatorname{dist}'(u) $$

となります．すべての頂点 $u$ のなかでこの値が最大のものが答えです．

提出コード