All Pairs Shortest Paths のアルゴリズムさんたち
前書き
全点対最短経路問題 (APSP : All Pair Shortest Path) を解くアルゴリズムを 4 つ紹介します。
$V$ 頂点 $E$ 辺の非負重み有向グラフ $G$ を考えます。 負の重みがあるときは一回 Bellman-Ford か何かを使ってポテンシャルを計算すれば非負に直せると思います。
お品書き
- Warshall-Floyd 法
- Dijkstra 法を $V$ 回
- Hidden Path Algorithm
- SHORT Algorithm
1,2 はお馴染み。
3,4 は資料も全然ないし使われてない印象。
どちらも Dijkstra を何度も回すのは無駄が多いから使いまわせるところを使いまわそうって発想のアルゴリズム。
1,2 を押さえておけば大抵の場合 (特に競プロ(非マラソン)) は問題なくて、 3,4 は少しでもいいから高速化したいときに使う可能性があるかもしれない…。
どちらも Introduction to Algorithms で軽く触れられているっぽい (ホントに触るだけ)
1. Warshall-Floyd
Floyd-Warshall 表記だったりもする。
- 計算量 $O(V^3)$
- 実装が超簡単
- グラフが密な時に(比較的)高速
for(int k: range(n)) for(int i: range(n)) for(int j: range(n)) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
これだけ。 kij の順番を間違えても 3 回繰り返すと正しい解が得られる (詳細はググって)。
証明は割と難しい
別名 Dkijstra法 (いいえ)
2. Dijkstra 法を $V$ 回
各頂点を始点に $V$ 回 dijkstra 走らせるという素直な発想。 性能も別に悪くない。
- 計算量 $O(V * f(V, E))$
$f(V, E)$ はダイクストラ法 1 回の計算量。実装によって色々- 二分ヒープ $O(V * (V+E) \log V)$
- フィボナッチヒープ $O(V * (E + V \log V))$ (持ってない)
- ヒープを使わないやつだと $O(V^3)$
- グラフが疎なら WF よりもこっち
負辺除去のために一度 bellman-ford でポテンシャルを出してから dijkstra を適用するものを Johnson's Algorithm というらしい。
Johnson's algorithm - Wikipedia
3. Hidden Path Algorithm
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths Karger - Google 検索
ネット上に解説がほとんどない。 ググると論文が転がっているけど合法なのかは知らない
- 計算量
- 二分ヒープ $O(V*E \log V)$
- フィボナッチヒープ $O(V*E + V^2 \log V)$
- 最短経路に関係する辺の数を $S$ として $O(V*S + V^2 \log V)$ になるらしい
グラフの形状にもよるけど多くのケースで $S = O(V \log V)$ ぐらいになるそう。 高速道路みたいなパスがあれば多くの最短経路に使われるので効いてくる。
Dijkstra のヒープに (距離, 頂点) じゃなくて (距離, パス) を積んで処理するイメージ。
- 最短経路 (u, w) になり得るパスは、すでに見つかっている最短経路 (u, v) の 後 に辺 (v, w) を付け足したもの
ただし、付け足される辺 (v, w) はそれ自体が最短経路 (v, w) である場合に限ってよい - 最短経路 (u, w) になり得るパスは、すでに見つかっている最短経路 (v, w) の 前 に辺 (u, v) を付け足したもの
ただし、付け足される辺 (u, v) はそれ自体が最短経路 (u, v) である場合に限ってよい
という骨子の元、ヒープに積んだパスを処理していく。
実装 https://gist.github.com/koyumeishi/5ff92c367e0b91f2a7a1d2b4aead158f#file-apsp-cpp-L85-L114
// パス p(u, v), q(v, w) を合成する auto update = [&](const path& p, const path& q){ path next_path{ p.from, q.to, p.dist + q.dist, p.next, }; if(next_path < shortest_path_[next_path.from][next_path.to]){ shortest_path_[next_path.from][next_path.to] = next_path; pq.push(next_path); // ヒープに追加 } }; while(!pq.empty()){ path p = pq.top(); pq.pop(); if(shortest_path_[p.from][p.to] < p) continue; // キャッシュの関係?で discovered_paths の工夫がない方が速い… // discovered_paths[p.from].push_back(p); // p.from を始点とする最短経路 if(p.next == p.to){ // is edge optimal_into_edges[p.to].push_back(p); // p.to に入ってくる辺 // 辺 の後ろに p.to を始点とする最短経路を合成 // for(const path& q: discovered_paths[p.to]){ for(const auto& q: shortest_paths_[p.to]){ update(p, q); } } for(const path& r: optimal_into_edges[p.from]){ // パスの前に p.from に入ってくる辺を合成 update(r, p); } }
4. SHORT Algorithm
All-Pairs Shortest Paths and the Essential Subgraph McGeoch - Google 検索
ググラビリティが非常に低い。
- 計算量
- Hidden Path Algorithm と同様 $O(V*S + V^2 \log V)$
最短経路に使われ得る辺のみからなる Essential Subgaph $H$ を、 各頂点 $v$ を始点とする最短経路木 $T(v)$ を構築しながら構築していく。
頂点 $v$ を始点とする Dijkstra法 の途中では距離が確定した頂点からなる木 $T(v)$ と、 $T(v)$ に隣接した次の最短頂点候補のヒープ $fringe(v)$ を管理している。
$T(v)$ に 辺$(v, w)$ の代替となるようなパス (距離が辺(u,v)以下のパス) が存在していればこの辺は不要、
存在していなければ $H$ に追加する。
$fringe(v)$ に追加する頂点は元々のグラフ $G$ ではなく $H$ に追加された辺のみを見ればよく、
$H$ と $T$ を適切に逐次更新していくことで無駄を省いている。
詳しくは論文をどうぞ。
実装 https://gist.github.com/koyumeishi/5ff92c367e0b91f2a7a1d2b4aead158f#file-apsp-cpp-L210-L261
auto dijkstra_process = [&](size_t v, size_t z, path e){ auto d = e.dist + shortest_path_[v][z].dist; path next_path{v, e.to, d, shortest_path_[v][z].next}; if(v == z) next_path = e; if(shortest_path_[v][e.to] > next_path){ fringe[v].push(next_path); } }; auto exists_alternate_path = [&](path p, bool is_postprocess = false){ const bool ACCEPT = false; const bool REJECT = true; size_t v = p.from; if(!is_postprocess && shortest_path_[p.from][p.to].dist <= p.dist) return REJECT; for(int z: T_nodes[v]){ for(auto& i=T[v][z]; i<(int)H[z].size(); i++){ auto& e = H[z][i]; dijkstra_process(v, z, e); } } while(true){ if(fringe[v].empty()) return ACCEPT; auto e = fringe[v].top(); if(!is_postprocess && e > p) return ACCEPT; fringe[v].pop(); size_t z = e.to; if(T[v][z] >= 0) continue; shortest_path_[v][z] = e; T_nodes[v].push_back(z); T[v][z] = 0; for(auto& i=T[v][z]; i<(int)H[z].size(); i++){ auto& e = H[z][i]; dijkstra_process(v, z, e); } if(!is_postprocess && z == p.to) return REJECT; } }; while(!pq.empty()){ path p = pq.top(); pq.pop(); if(exists_alternate_path(p) == false) { H[p.from].push_back(p); } } // postprocessing for(size_t i=0; i<n_; i++){ exists_alternate_path(path{i, i, -1}, true); }
ベンチマーク
どんなグラフを使えばいいのかよくわからなかったので
Graph500 にも使われている
Stochastic Kronecker Graphs というグラフ生成法を試してみた。
これも面白いアルゴリズム。
実社会のグラフの特徴量に寄せるパラメータ調整をして、似た特徴のグラフをランダム生成するのに使われているっぽい？
生成したグラフ
- 無向グラフ
- 非連結の可能性あり
- 重み一様ランダム
- SCALE = 10 ( |V| = 1024 )
- Weight = {{0.57, 0.19}, {0.19, 0.05}} (Graph500 と同一)
- ヒープには std::priority_queue を使用 (フィボナッチヒープに変えれば速くなる可能性アリ)
グラフの特徴としては疎密があって割と実社会のネットワークに近いものだと思う。
edge_factor を変えて試してみた。 (|E| = |V| * edge_factor)
二重辺/自己辺は除去するので実際は辺数はずっと少なくなる。
| edge_factor | Warshall-Floyd [ms] | V-times Dijkstra [ms] | HiddenPath [ms] | SHORT [ms] |
|---|---|---|---|---|
| 8 | 766 | 142 | 106 | 90 |
| 16 | 795 | 187 | 142 | 109 |
| 32 | 789 | 232 | 184 | 120 |
| 64 | 765 | 232 | 269 | 131 |
| 128 | 758 | 314 | 336 | 150 |
| 256 | 775 | 365 | 523 | 162 |
| 512 | 771 | 382 | 704 | 184 |
| 1024 | 773 | 432 | 1214 | 196 |
| 2048 | 787 | 500 | 1568 | 242 |
少なくともこのグラフにおいては SHORT Algorithm が優秀。
密になったときの Hidden Path Algorithm がなんか思ったより遅いんだけど、
多分ヒープにパスを沢山詰め込んでるせいで log は定数と言い張れなくなってる。
フィボナッチヒープに切り替えるとマシになるかも。 (フィボナッチヒープは想像上にしか存在していない)
あとがき
dijkstra を何回も走らせるのもったいないなぁと思っていたのでちょっと調べました。
この子達使う機会あるかなぁ……？ 面白かったからいいんだけど。
他にも "重み一様ランダムな完全グラフなら高確率で $O(V^2)$" とか、
全点間じゃなくて複数点間距離を計算したいときに活躍するアルゴリズムとか存在してそうでした。
実用上は dijkstra と warshall-floyd だけ知ってればいいと思います。 おしまい。
