目次
Hub-Labeling
経路探索に速さを求めて行き着いた先
潤沢なメモリが利用できるなら、どんなノード間でも数nsで最短距離を算出可能
概要
事前計算とクエリに分かれる。「Hubノード」という概念を利用する。
- 事前計算
- 「Hubノード」を適切に選ぶ
- 全ノードに対し、いくつかの「Hubノード」までの最短距離を持たせる
- クエリ
- $s$ から $t$ までの最短経路の距離を求めるとする
- $s$ と $t$ で共通して持っている「Hubノード」を探し、距離を合算
- その中で最小のものが最短距離
- そのため「Hubノード」は以下の条件を満たすように選ぶ
- 全ての2ノードの組で必ず1つは共通Hubノードがある
- その合計が最短距離となる
(s) s が持つHubノードID 15 23 25 41 ...
Hubノードまでの距離 10 11 9 6 ...
(t) t が持つHubノードID 11 23 26 41 ...
Hubノードまでの距離 8 19 11 19 ...
~~ ~~ 共通ノードは23,41
↓ ↓ 距離を合算
最短距離は25 30 25
要求スペック
（Hub Labeling Algorithmsより引用）
西ヨーロッパのネットワーク、1800万ノード・2400万リンクで、
- 事前計算に時間のかからない簡単な実装で
- ノード1つ当たりに持たせる平均Hubノード数: 98
- メモリ: 22.5GB
- 計算時間: 700ns
- 頑張ってHubノードを厳選すれば、
- ノード1つ当たりに持たせる平均Hubノード数: 69
- メモリ: 17.7GB
- 計算時間: 508ns
多少重いが、今どき用意できないスペックなんてことは全然無い
