乗り換え案内やカーナビなどを使って最短経路や最安経路を検索したことがある人は多いと思います。あれ便利ですよね。ですが、どのようにしたらそのような検索ができるのか？と考えたことはないでしょうか。
この記事では数ある最短経路探索アルゴリズムの中からDijkstra法を紹介します。
Dijkstra法とは
Dijkstra法は、グラフのある特定の一頂点から他のすべての頂点への最短経路を探すことができるアルゴリズムです。
例えば下のグラフで頂点1から他の頂点に向かうのに最短の経路を探すことができます。
最短距離の求め方
始点から他の頂点までの最短距離を確定させていくことを考えます。
次のような考え方で距離を確定させていきます。
- 始点からの最短距離が確定した頂点を探す。
- 1.で見つかった頂点と隣接する頂点の距離を更新する。
- 1.で見つけた頂点をその後再度更新に利用することはない。
上の手順を繰り返すことですべての頂点への最短距離を確定させます。
具体的な例を出すとこんな感じです。
/*
start : 始点
graph : 隣接行列
graph[i][j] := i -> jの距離(i,jが隣接していない場合は正の十分大きな数)
*/
fn dijkstra(start : usize,graph: &Vec<Vec<u64>>) -> Vec<u64> {
let sz = graph.len();
//dist : dist[i] := startからiまでの最小距離
let mut dist = vec![1u64 << 60; sz];
let mut used = vec![false; sz];
dist[start] = 0;
loop {
let mut v = sz + 1;
for u in 0..v {
if !used[u] && (v == sz + 1 || dist[u] < dist[v]) {
v = u;
}
}
// 最小コストが確定した頂点がない、つまり全頂点確定済み
if v == sz + 1 {
break;
}
used[v] = true;
for u in 0..sz {
dist[u] = std::cmp::min(dist[u], dist[v] + graph[v][u]);
}
}
dist
}
このコードの計算量なのですが、頂点集合をVとすると一度のループの中で$O(|V|)$回for式が回ります。それを頂点の数だけ繰り返すので$O(|V|^{2})$になります。
この方法だと頂点数が100000くらいになると実行時間がとんでもないことになります。ですので、どうにか高速にできる場所がないか考えてみます。
疎グラフ(頂点数に比べて辺の数が比較的少ないグラフ)を考えます。まず、隣接リストを使うことで最短距離更新の際に各辺をちょうど1度だけ見るので最短距離更新にかかる計算量は辺集合をEとして、$O(|E|)$となります。
他に時間がかかっていそうなのは最短距離を確定させる部分ですので、この部分を高速化できるか考えます。この部分は、BinaryHeapやPriorityQueueを用いることで距離が小さい順に最短距離の確定を行うことができるようになります。同じ頂点に対してBinaryHeapから何回も要素を取り出す場合もありますが、最初に取り出したもの以外については最短距離でなければ無視すればよいです。BinaryHeapの要素数は頂点数に比例して増えるため$O(|V|)$です。$|E|$回BinaryHeapの更新、取り出しを行うため、計算量は$O(|E| \log |V|)$となります。
具体的なコードです。
/*
graph : 隣接リスト
graph[i][j] := (iと隣接しているj個目の頂点, 距離)
*/
fn dijkstra(graph: &Vec<Vec<(usize, u64)>>, start: usize) -> Vec<u64> {
let n = graph.len();
let mut pq = std::collections::BinaryHeap::new();
let mut dist = vec![1u64 << 60; n];
//距離の小さい順に取りたいので(距離,頂点)のペアでBinaryHeapに突っ込む
pq.push(std::cmp::Reverse((0, start)));
dist[start] = 0;
while let Some(v) = pq.pop() {
let (cost, now) = v.0;
//取り出したものが最短距離でないときに無視
if dist[now] < cost {
continue;
}
for (to, c) in &graph[now] {
//すでにdistに入っている距離を更新できる場合はBinaryHeapに突っ込んでdistを更新
if dist[*to] > *c + dist[now] {
dist[*to] = dist[now] + *c;
pq.push(std::cmp::Reverse((dist[*to], *to)));
}
}
}
dist
}
最短経路の求め方
ここまでは最短「距離」を求めてきましたが、実際に最短の「経路」、つまりどのように頂点をたどればその距離を実現できるのか、という具体的な経路を求めていきます。電車に乗って目的地に行きたいのに何分で着くかだけ教えて乗り換えや路線を教えてくれないのは嫌ですよね。
最短距離を求める際にどのようにして更新を行っていたかを思い出しましょう。頂点vの更新を行うには頂点vと隣接していて最短距離が確定している頂点uを用いて、dist[v] = dist[u] + (uからvへの距離)というように更新していました。このときに、vの更新を頂点uを用いて行ったというのを記録しておけばよいです。その記録を用いて最短経路を復元することができます。
具体的なコードです。
/*
graph : 隣接リスト
graph[i][j] := (iと隣接しているj個目の頂点, 距離)
*/
fn dijkstra(graph: &Vec<Vec<(usize, u64)>>, start: usize) -> (Vec<u64>,Vec<usize>) {
let n = graph.len();
//どの頂点を使って更新を行ったかの記録用
let mut prev = vec![n + 1;n];
let mut pq = std::collections::BinaryHeap::new();
let mut dist = vec![1u64 << 60; n];
//距離の小さい順に取りたいので(距離,頂点)のペアでBinaryHeapに突っ込む
pq.push(std::cmp::Reverse((0, start)));
dist[start] = 0;
while let Some(v) = pq.pop() {
let (cost, now) = v.0;
//取り出したものが最短距離でないときに無視
if dist[now] < cost {
continue;
}
for (to, c) in &graph[now] {
//すでにdistに入っている距離を更新できる場合はBinaryHeapに突っ込んでdistを更新
if dist[*to] > *c + dist[now] {
dist[*to] = dist[now] + *c;
prev[*to] = now;
pq.push(std::cmp::Reverse((dist[*to], *to)));
}
}
}
dist
}
// _tへの最短距離を求める関数
fn get_shortest_path(_t: usize, prev: &Vec<usize>) -> Vec<usize> {
let mut t = _t;
let stopper = prev.len() + 1;
let mut shortest_path = Vec::new();
while t != stopper {
shortest_path.push(t);
t = prev[t];
}
shortest_path
}
最後に
久々にRust書いたので楽しかったです。
最短距離の求め方について少しイメージができたでしょうか。これを機に皆さんにアルゴリズムに興味を持っていただけると嬉しいです。
参考
GRAPH×GRAPH
アルゴリズムロジック 入門レベルからのアルゴリズム解説サイト ダイクストラ法による単一始点最短経路を求めるアルゴリズム
秋葉拓哉、 岩田陽一、 北川宜稔. プログラミングコンテストチャレンジブック [第2版] 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える,マイナビ, 2012, pp.96~pp.99