Rustでダイクストラ法 (優先度つきキューと一緒)
TL;DR
- 重みのある無向辺グラフの任意の点の最短経路を求める方法の一つがダイクストラ法
- 訪問したノードに始点からの最短距離を記録
- 候補を待ち行列に入れて､各点の最短距離を更新する
- 優先度付きキューを扱う場合､
std::collections::BinaryHeapを使う- Min-Heapにしたい場合は`BinaryHeap<Reverse<T>>
- (または目標値を構造体でラップして
Ordトレイトを実装する(後述))
- (または目標値を構造体でラップして
- 挿入コストは
O(\log_2 N) N - 最大(最小)要素を取り出すのは
O(1)
- Min-Heapにしたい場合は`BinaryHeap<Reverse<T>>
はじめに
std::collections::BinaryHeapについては以下のスクラップを参照のこと↓
GitHub Repo
Dijkstra Algo.(ダイクストラ法)
詳しいことはいろんな解説記事にぶん投げますが､
地下鉄やバスの路線図があって､駅Aから駅Bまで行く最短ルートはなにかのときに有効なアルゴリズム
(ref: Wikipedia)
ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである｡
グラフ使う式や変数の簡単な説明
-
G -
V -
E -
Q
待ち行列の選択
Dijkstra法の実現には､路線図となるグラフ
おおまかなアルゴリズムは上記の通り｡
- 配列
- 初期化時点で
Q \leftarrow V -
Qからd(u)が最小のノードを取り出す
- 初期化時点で
- 優先度付きキュー
- 取り出す処理が先頭から取り出す処理になるので計算量を減らすことができる
-
alt Q.push(v) - 2分木ヒープとフィボナッチヒープのようにいくつか選択肢がある
フィボナッチヒープ正直理解してn
Rustの実装
グラフを扱うとき､よく出てくるのは隣接行列で､行と列の番号がノード､要素の値が辺の重みを表す｡今回扱う非負整数を重みにもつ無向グラフは､すべての要素が非負整数の対称行列を考えればよい｡
BinaryHeapの使い方
ダイクストラ法(優先度付きキューの場合)の､
- 待ち行列から始点までの最短経路が最小のものを取り出す
- 隣接辺で距離が更新されたノードを追加する
この2つの処理をpop()/push()で対応できる｡
待ち行列while letが使用できる｡
条件分岐の記述はRust By Examplesなどを参考にすると良い｡
Max-HeapをMin-Heapとして振る舞わせる
RustのBinaryHeapは先頭が最大値になるMax-Heapとして実装されているので｢最小値を取り出す｣Min-Heapではない｡
挙動についてはスクラップで解説している｡
Min-HeapとしてのBinaryHeapの実装は2通りある｡
①Reverse<T>でWrapする
std::cmp::Reverseは､比較演算可能な2値の比較結果を逆にする事ができる｡
スクラップでA*法にBinaryHeapを適用させており､このときも要素をReverseでWrapするだけなので簡素でわかりやすい実装である｡
ただReverse<T>からTを取り出したいときが持って回った書き方になるので注意｡
使用例:
追記:
- 普通にバインドすれば行ける
- 構造体作るよりタプル実装のほうが楽
(2025/03/09追記)
ので､リファクタしました 変なStruct生やすより見やすいですね
https://github.com/raiga0310/dijkstra-with-binary-heap/commit/6998989767f0a740ca6d6bbb6c6803da9f2f709f
②Ordトレイトの実装で演算を書き換える
待ち行列にいれる際に､単に整数型で管理するのではなく､構造体でラップし､その構造体について演算を定義することで演算子を利用できる｡
本来Ordトレイトのcmp()実装はself.cmp(&other)のような形式をとることで自然な演算結果になるのだが､ここではそれを逆転することで､｢BinaryHeapは最大値を先頭におけるように振る舞っているが､其の実最小値を先頭におくように振る舞う｣実装になっている｡
(平子隊長の斬魄刀みたいなものです)
テクニカルで実装も楽なので色々とお得な面もあるが､高機能な関数に組み込む場合認知負荷が無意識のうちにかかる可能性が高いので､多少記述が長くなるとしてもReverseで宣言的に書いたほうがよい(どうせコンパイルされたバイナリが実行されるんだからソースコードはやってることが明示できたほうが人間にやさしい)
実行結果
cargo run
Compiling dijkstra-with-binary-heap v0.1.0 (C:\Users\raiga\dev\dijkstra-with-binary-heap)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.06s
Running `target\debug\dijkstra-with-binary-heap.exe`
現在のノード: 0, 最短距離: 0
計算するノード: 1
各ノードと始点sとの最短距離
0, -, -, -, -, -, -, -, -, -,
更新: ノード 1 の最短距離を 3 に変更
現在のノード: 0, 最短距離: 0
計算するノード: 5
各ノードと始点sとの最短距離
0, 3, -, -, -, -, -, -, -, -,
更新: ノード 5 の最短距離を 6 に変更
現在のノード: 0, 最短距離: 0
計算するノード: 9
各ノードと始点sとの最短距離
0, 3, -, -, -, 6, -, -, -, -,
更新: ノード 9 の最短距離を 9 に変更
===========================================================
現在のノード: 1, 最短距離: 3
計算するノード: 0
各ノードと始点sとの最短距離
0, 3, -, -, -, 6, -, -, -, 9,
現在のノード: 1, 最短距離: 3
計算するノード: 2
各ノードと始点sとの最短距離
0, 3, -, -, -, 6, -, -, -, 9,
更新: ノード 2 の最短距離を 4 に変更
===========================================================
現在のノード: 2, 最短距離: 4
計算するノード: 1
各ノードと始点sとの最短距離
0, 3, 4, -, -, 6, -, -, -, 9,
現在のノード: 2, 最短距離: 4
計算するノード: 3
各ノードと始点sとの最短距離
0, 3, 4, -, -, 6, -, -, -, 9,
更新: ノード 3 の最短距離を 11 に変更
現在のノード: 2, 最短距離: 4
計算するノード: 7
各ノードと始点sとの最短距離
0, 3, 4, 11, -, 6, -, -, -, 9,
更新: ノード 7 の最短距離を 8 に変更
===========================================================
現在のノード: 5, 最短距離: 6
計算するノード: 0
各ノードと始点sとの最短距離
0, 3, 4, 11, -, 6, -, 8, -, 9,
現在のノード: 5, 最短距離: 6
計算するノード: 4
各ノードと始点sとの最短距離
0, 3, 4, 11, -, 6, -, 8, -, 9,
更新: ノード 4 の最短距離を 11 に変更
現在のノード: 5, 最短距離: 6
計算するノード: 6
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, -, 8, -, 9,
更新: ノード 6 の最短距離を 14 に変更
===========================================================
現在のノード: 7, 最短距離: 8
計算するノード: 2
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, -, 9,
現在のノード: 7, 最短距離: 8
計算するノード: 6
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, -, 9,
現在のノード: 7, 最短距離: 8
計算するノード: 8
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, -, 9,
更新: ノード 8 の最短距離を 9 に変更
===========================================================
現在のノード: 9, 最短距離: 9
計算するノード: 0
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 9, 最短距離: 9
計算するノード: 3
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 9, 最短距離: 9
計算するノード: 8
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
===========================================================
現在のノード: 8, 最短距離: 9
計算するノード: 7
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 8, 最短距離: 9
計算するノード: 9
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
===========================================================
現在のノード: 3, 最短距離: 11
計算するノード: 2
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 3, 最短距離: 11
計算するノード: 4
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 3, 最短距離: 11
計算するノード: 9
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
===========================================================
現在のノード: 4, 最短距離: 11
計算するノード: 3
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 4, 最短距離: 11
計算するノード: 5
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
===========================================================
現在のノード: 6, 最短距離: 14
計算するノード: 5
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
現在のノード: 6, 最短距離: 14
計算するノード: 7
各ノードと始点sとの最短距離
0, 3, 4, 11, 11, 6, 14, 8, 9, 9,
===========================================================
最短経路: [0, 1, 2, 7, 8]
始点0から終点8までの最短距離: 9
まとめ､あるいは感想
- Dijkstra法は名前だけだと難しそうに聞こえるが､やっていることは単純
- Rustでの実装は
while letをはじめとする標準の機能が手厚いのでむしろ手が出しやすい部類 みんなRustをやろうな - この実装では全てのノードの始点からの最短経路を求めているが､ゴールの距離が確定したと判断できるなら途中で打ち切るヒューリスティックな実装もありかもしれない(見込みのない辺を刈るとか)
Discussion