ダイクストラ法について
アルゴリズムを学んでいく中でダイクストラ法というものを目にし、以前のABCコンテストのDを解くときに調べてた記憶があったので、この度勉強してまとめることにしました。
まだまだ内容が薄かったり、コードが冗長だったりすると思いますが、勉強の記録程度で見ていただけると嬉しいです。
ダイクストラ法とは
難しい言葉で説明すると理解しにくいと思うので、下の図で説明します。丸で囲まれた数字を頂点、頂点から頂点に向かって伸びている矢印が移動できる方向、矢印の近くにある数字がその頂点に移動するためにかかるコスト(時間))とします。
頂点:0(スタート)から頂点:5(ゴール)まで最短時間でどのくらいで行けるか を求めるアルゴリズムです。
この説明を踏まえた上で、Wikipediaの言葉を引用します。
ダイクストラ法(だいくすとらほう、英: Dijkstra's algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能であるが、実用性はあまり高くない。
また、グラフについてです。
グラフ(英: Graph)とは、ノード(頂点)群とノード間の連結関係を表すエッジ(枝)群で構成される抽象データ型、and・orその実装である具象データ型である。グラフ理論を基盤として、なんらかの証明が可能であったり、豊富なアルゴリズムが利用できること、などが特徴である。
???となる方も多いと思います。この記事を書いてる時の私もあまり理解していないです…
身近なところでいうと、カーナビなどに使われているようです。
注意点として、負のコストを持つグラフには使えないことが挙げられます。
負のコストは、時間→払うお金 としてお金+物で物々交換をイメージして下さい。どのように物を交換すれば一番安く手に入れることができるかという探索において、お金を払う = 正のコスト お金を貰う = 負のコスト と考えるとイメージがしやすいと思います。
アルゴリズム
これもまた、分かりにくいと思います(後で、実際のコードを交えながら図解します)
- スタート位置を決め、スタートに現在位置を設定する。
- スタート位置を訪問済み、訪れていない頂点を未訪問とする。
- スタートから、スタート以外の頂点へのコストを無限大とする。
- 現在位置から隣接している未訪問の頂点の現在位置からその頂点までのコストを参照する。
- 現在位置までのコストと参照したコストの合計が、現在設定されてるコストより小さければコストを更新する。
- ゴールを除く未訪問の頂点の中から、最小コストの頂点を現在位置とする
- すべての頂点が訪問済みとなるまで、4~6を繰り返す。
ダイクストラ法の実装
優先度付きキューについて
(2020/04/30 追記)
優先度付きキューとは、要素に優先度をつけ、最も優先度の高い要素を取り出すことのできるデータ型です。
C++では、標準ライブラリにpriority_queueという名前で定義されており、パラメータにより優先度のつけ方を変更できます。
ダイクストラ法では、コストが一番小さい頂点を取り出す際に用いることができます。
この記事の執筆時にはまだ優先度付きキューの存在を知らなかったため、使用していませんでしたが学ぶ機会があったため、優先度付きキューを使用したダイクストラ法のコードも併せて載せたいと思います。
また、アルゴリズム的に変更点はほぼないので、コード解説は優先度付きキュー未使用の方で行っています。
コード(優先度付きキュー未使用)
C++で実装を行います。
#include<iostream> #include<vector> #include<stack> using namespace std; int main() { vector<vector<int>>node(10, vector<int>(0)); vector<vector<int>>cost(10,vector<int>(10)); vector<int> unVisited; stack<int> S; int N,C,a,b,c,erase = 0,position = 0; cin >> N >> C; for (int i = 0; i < N; i++) { cin >> a >> b >> c; node[a].push_back(b); //[i][j]で[i]の隣接グラフのj個目 cost[a][b] = c; //node間移動のコスト格納 } vector<int>root(C,INT32_MAX); vector<bool>isDiscovery(C, false); vector<int>before(C, 0); root[position] = 0; unVisited.push_back(0); //スタートの頂点を格納 do{ /*発見済みの未訪問の頂点の中で一番コストが低いものを選択*/ position = INT32_MAX; for (int i = 0; i < unVisited.size();i++) { if(root[unVisited[i]] < position){ position = root[unVisited[i]]; erase = i; } } /*次の移動位置に設定し、訪問する頂点を削除する*/ position = unVisited[erase]; unVisited.erase(unVisited.begin() + erase); /*現在の頂点から隣接する頂点のコストを見て、コストが低くなる場合更新*/ for (int nextNode : node[position]) { if (root[nextNode] > cost[position][nextNode] + root[position]) { root[nextNode] = cost[position][nextNode] + root[position]; before[nextNode] = position; //頂点のコストを更新した、頂点を記録 } /*発見済みかつ、未訪問のゴール以外の頂点を記録*/ if (!isDiscovery[nextNode] && nextNode != C - 1) { unVisited.push_back(nextNode); isDiscovery[nextNode] = true; } } } while (!unVisited.empty()); //未訪問の頂点がなくなるまで繰り返す /*最短経路の頂点を出力*/ S.push(C - 1); for (int i = 0; i < C;i++) { S.push(before[S.top()]); if (!S.top()) break; } while (!S.empty()) { cout << S.top() << " "; S.pop(); } cout << endl << root[C - 1] << endl; }
コード(優先度付きキュー使用)
#include<iostream> #include<vector> #include<stack> #include<queue> using namespace std; int main() { vector<vector<int>>node(10, vector<int>(0)); vector<vector<int>>cost(10,vector<int>(10)); priority_queue<int,vector<int>,greater<int>> q; stack<int> S; int N,C,a,b,c,position = 0; cin >> N >> C; for (int i = 0; i < N; i++) { cin >> a >> b >> c; node[a].push_back(b); //[i][j]で[i]の隣接グラフのj個目 cost[a][b] = c; //node間移動のコスト格納 } vector<int>root(C,INT32_MAX); vector<bool>isDiscovery(C, false); vector<int>before(C, 0); root[position] = 0; //スタートの頂点を格納 q.push(0); do{ /*発見済みの未訪問の頂点の中で一番コストが低いものを取り出す*/ position = q.top(), q.pop(); /*現在の頂点から隣接する頂点のコストを見て、コストが低くなる場合更新*/ for (int nextNode : node[position]) { if (root[nextNode] > cost[position][nextNode] + root[position]) { root[nextNode] = cost[position][nextNode] + root[position]; before[nextNode] = position; //頂点のコストを更新した、頂点を記録 } /*発見済みかつ、未訪問のゴール以外の頂点を記録*/ if (!isDiscovery[nextNode] && nextNode != C - 1) { q.push(nextNode); isDiscovery[nextNode] = true; } } } while (!q.empty()); //未訪問の頂点がなくなるまで繰り返す /*最短経路の頂点を出力*/ S.push(C - 1); for (int i = 0; i < C;i++) { S.push(before[S.top()]); if (!S.top()) break; } while (!S.empty()) { cout << S.top(); S.pop(); if (S.size() != 0) cout << " -> "; } cout << endl << root[C - 1] << endl; }
コード解説(優先度付きキュー未使用)
このコードで探索を行うグラフは先ほどの図となります。
簡単にコードの解説を行います。
vectorでは次の値を格納しています。
- 頂点に隣接している頂点:node
- 頂点間の移動にかかるコスト:cost
- 発見済みで未訪問の頂点:unVisited
- スタート位置から各頂点への最短コスト:root
- 隣接した頂点が発見済みかどうかの真偽:isDiscovery
- 頂点へのコストが更新された時の現在位置:before
入力は、頂点(a)から頂点(b)までのコスト(c)を一区切りとして、
入力数N,、頂点数C,N回のa b cとなります。
隣接する頂点、移動にかかるコストを格納し、初期化(各頂点へのコスト無限大、各頂点に未訪問を設定、コスト更新時の現在位置を0)します。
スタートを0に設定し、ループへ
~~ループ~~
- 発見済みで未訪問の頂点の中で一番コストが低いものを現在位置に設定
- 現在位置から隣接する頂点の、スタートからのその頂点までのコスト(スタートからのコスト)が更新できる場合は更新
- 発見した未訪問でゴール以外の頂点を記録
~~ループ~~
ループを抜けたら、どの経路できたかをスタックで出力。(Stack使ってみたかっただけです)
実行
・入力値
9 6 0 1 5 0 2 2 1 3 4 1 4 2 2 1 8 2 4 7 3 4 6 3 5 3 4 5 1
・出力
0 1 4 5 8
実行の図解
※青の頂点は現在位置、水色の数字はスタートからのコストを表しています。
1. 初期化
左: グラフを作成します
右: スタートからのコストを設定します。
※青の矢印は隣接ノードを調べている時、赤の破線の矢印はスタートからの移動経路、数字はコストの更新、濃い灰色の頂点は訪問済みを表しています。
2.ループ1回目
左: 頂点0に隣接した、頂点1及び2に設定されているスタートからのコストより、0+5=5、0+2=2のほうが小さいので更新します。
中: ゴール以外の頂点かつ、発見済みで未訪問の頂点1及び2で一番移動コストが少ない頂点を調べ、頂点2の2コストと分かります。
右: 頂点2に移動します。
3.ループ2回目
左: 頂点2に隣接した、頂点4に設定されているスタートからのコストより、2+7=9のほうが小さいので更新します。頂点1は設定されている方が小さいので更新はしません。
中: ゴール以外の頂点かつ、発見済みで未訪問の頂点1及び4で一番移動コストが少ない頂点を調べ、頂点1の5コストと分かります。
右: 頂点1に移動します。
4.ループ3回目
左: 頂点1に隣接した、頂点3及び4に設定されているスタートからのコストより、5+4=9、5+2=7のほうが小さいので更新します。
中: ゴール以外の頂点かつ、発見済みで未訪問の頂点3及び4で一番移動コストが少ない頂点を調べ、頂点4の7コストと分かります。
右: 頂点4に移動します。
5.ループ4回目
左: 頂点4に隣接した、頂点5に設定されているスタートからのコストより、7+1=8のほうが小さいので更新します。
中: ゴール以外の頂点かつ、発見済みで未訪問の頂点3で一番移動コストが少ない頂点を調べ、頂点3の9コストと分かります。
右: 頂点3に移動します。
ループを抜けて
左: 頂点3に隣接した、頂点5に設定されているスタートからのコストのほうが、9+3=12より小さいため更新はしません。ここでループを抜けます。
右: ゴール以外が訪問済みとなったため、頂点5に移動して終了です。