最短経路問題に対するコストスケーリング法
できること
$ N頂点$ M辺の整数重み有向グラフが与えられる（重みは負でもよい）
辺の重みがすべて$ -C以上であるとき、最短路を$ O(\sqrt{N} M \log C)で求めることができる
概略
コストスケーリング法によって、feasibleなポテンシャルを求めることができる
feasibleなポテンシャルが求まれば、ダイクストラ法を適用することにより$ O(M \log N)の追加コストで最短路が求まる
feasibleの条件を緩和した$ \varepsilon-feasibleなポテンシャルを求め、Refine操作によって$ \varepsilonを半分ずつ減らしていく（スケーリング）ことで、最終的にfeasibleなポテンシャルを求める
Refine操作：$ 2\varepsilon-feasibleなポテンシャルから$ \varepsilon-feasibleなポテンシャルをつくる
1. Decycle操作：強連結成分を縮約する
2. グラフから$ \varepsilon-improvableな頂点のみ取り出し、これに対して$ u \to vのパスで最後に$ \varepsilon-improvableな辺を通るものがあるときに辺$ u \to vを張ったグラフを考える（このグラフの頂点数を$ kとする）
このグラフには要素数$ \sqrt k以上のchain又はantichainが存在する
3. 以下のどちらかを行う
要素数$ \sqrt k以上のchainがあれば、そのchainに対してEliminate-Chain操作を行う
そうでなければ、
5. $ \varepsilon-improvableな頂点がなくなれば終了
記号・用語の定義
記号・用語の定義：
$ c(u, v)：辺$ u \to vの重み
$ d(u, v)：$ u \to vの最短距離
$ \pi(v)：頂点$ vのポテンシャル
$ \pi(u, v)：ポテンシャルの差。$ \pi(v) - \pi(u)
被約コスト$ c^\pi(u, v)：$ c(u, v) - \pi(u, v)（feasibleなポテンシャルでは必ず非負になる）
ポテンシャルがfeasible：どの辺$ u \to vについても、$ c^\pi(u, v) \ge 0
ポテンシャルが$ \varepsilon-feasible：どの辺$ u \to vについても、$ c^\pi(u, v) > -\varepsilon（1-feasible＝feasible）
辺が$ \varepsilon-improvable：辺$ u \to vであって$ c^\pi(u, v) \le -\varepsilonであるもの
頂点が$ \varepsilon-improvable：頂点$ vであって$ \varepsilon-improvableな辺$ u \to vが存在するもの
辺がadmissible：辺$ u \to vであって$ c^\pi(e) \le 0であるもの
admissible graph$ G^\pi：元のグラフからadmissibleな辺のみとりだしたもの
閉包$ \overline{S}：$ Sから到達できる頂点集合
閉集合：$ S = \overline{S}となる集合（なお、どのような$ Sに対しても$ \overline Sは閉集合となる）
ポテンシャル
最短路双対において出てくる用語
グラフの頂点に対して割りと自由に決めることができる
ポテンシャルの差は最短距離に対応している
線形計画問題の強双対性により、ポテンシャルを求めると最短距離も求まる
主問題：グラフにおける$ s\to tの最短距離を求める
双対問題：feasibleなポテンシャルにおける$ \pi(s, t)の最大値を求める
Decycle操作
admissible graph$ G^\piの強連結成分を縮約する
このとき、縮約された頂点のポテンシャルは、強連結成分の中の頂点をひとつ選び採用する（どの頂点を選んでも、その後の操作による変化量は等しい）
縮約された頂点から出る辺のコストは、選んだ頂点～強連結成分の出口となる頂点までのコストを足す
このとき、ひとつの強連結成分に属している負辺があれば、その強連結成分全体が負閉路であり、そこから到達可能な頂点はすべて考える必要がない
負閉路といえるわけ：admissible graphの辺のコストは$ 0以下であるため、負辺を打ち消すことができないから
なお、すべての負閉路をこの段階で見つけられるわけではない
Cut-Relabel操作
admissible graph$ G^\pi上の閉集合$ Sが与えられたとき、それらの頂点のポテンシャルを$ \varepsilon減らす
この操作によって$ \varepsilon-improvableな辺は増加しない
Eliminate-Chain操作
admissible graph$ G^\pi上のパスが与えられたとき、パス上の始点を除く$ \varepsilon-improvableな頂点に対して後ろの方から閉包を取ってCut-Relabel操作を行う
このとき、Cut-Relabel操作を行っても$ \varepsilon-improvableなままなら、グラフには負閉路が含まれる
距離関数$ d'
$ G^\piでの距離関数$ d'を定義する
辺$ (u, v)の長さを、improvableなら$ -1、そうでなければ$ 0と定義する
このグラフ上での始点からの距離を$ d'とする
$ G^\piはDAGであるため、$ O(N)で計算できる
Refine
$ kを$ \varepsilon-improvableな頂点の個数、$ Dを$ \max_v (-d'(v))とする
$ D\ge \sqrt kなら、始点からの$ d'(v) = Dへのchainは$ \sqrt k本以上の$ \varepsilon-improvableな辺を含む
$ D < \sqrt kなら、$ \sqrt k個以上の$ \varepsilon-improvableな頂点を含むantichainが存在する
code:rust
fn refine() {
loop {
let decycled = decycle(&graph, &p0);
todo!();
}
}
Refine-P
全体は$ O(\sqrt n m \log C)で動作する
以下の繰り返し
1. Decycle操作：負閉路検出、長さ$ 0のadmissibleな閉路を削除
2. 距離$ d'を計算
3.
参考