ダイクストラ法

ダイクストラ法とは

　グラフのすべての頂点に対して、ある頂点からの最短距離を求めるアルゴリズム。

　辺のコスト (距離) は非負である必要がある。

　例えば、こんなグラフから、

このように、頂点 0 からの距離 d を求められる。

ダイクストラ法のアルゴリズム

1. スタート地点の頂点からその頂点自身への距離は 0 で最短距離として確定し、その頂点を u とおく。それ以外の頂点の距離は無限大としておく。


2. すべての頂点への最短距離が確定するまで、以下の操作を繰り返す。

• u からの辺がある、すべての頂点 v の距離を、[v の距離] と [(u の距離) + (辺 (u → v))] のうち小さいほうに更新する。
• 確定していない頂点のうち、距離が最も小さいものを最短距離として確定し、その頂点を u とおく。

例と証明っぽいやつ

ダイクストラ法の動き (GIF)

説明

　スタート地点を頂点 0 とする。

　辺のコストは 0 以上なので、スタート地点の最短距離は 0 で確定する。

　頂点 0 から 1 ステップ (1 回の移動) で行ける頂点 (頂点 1、頂点 2) の距離を更新する。

　(頂点 1: (初期値: ∞) → (頂点 0 の最短距離: 0) + (頂点 0 から 頂点 1 への辺のコスト: 2) = 2)

　(頂点 2: ∞ → 0 + 7)

　この時点で、確定していない頂点 1 ~ 4 のうち、距離が最小の頂点、頂点 1 を最短距離と確定できる。

　(証明的なやつ: 今、頂点 0 から 1 ステップで行ける経路の探索をした。それ以外で、頂点 1 にたどり着くには、頂点 0 から 2 ステップ以上移動しなくてはならない。頂点 0 から 1 ステップ移動するときの最短距離は、頂点 1 に行く場合で、距離は 2 である。辺のコストは非負なので、2 ステップ移動する距離は 2 以上だとわかる。なので、頂点 1 の距離 2 は最短距離であるとわかる。)

　次は、新たに確定した頂点、頂点 1 から 1 ステップで行ける頂点の距離を更新する。

　(頂点 2: 7 ≦ 2 + 6 なので変化なし、頂点 3: ∞ → 2 + 2)

　この時点で、確定していない頂点 2 ~ 4 のうち、距離が最小の頂点、頂点 3 を最短距離と確定できる。

　(証明的なやつ (さっきとほぼ同じだけど):  この時点で、最短距離が確定している頂点 (頂点 0、1) から 1 ステップで行ける経路の探索が終わっている。それ以外で、頂点 3 にたどり着くには、最短距離が確定している頂点 から 2 ステップ以上移動しなくてはならない。最短距離が確定している頂点 から 1 ステップ移動するときの最短距離は、頂点 3 に行く場合で、距離は 4 である。辺のコストは非負なので、2 ステップ移動する距離は 4 以上だとわかる。なので、頂点 3 の距離 4 は最短距離であるとわかる。)

　同様にして、新たに確定した頂点、頂点 3 から 1 ステップで行ける頂点の距離を更新する。

　確定していない頂点 2、4 のうち、頂点 4 の距離が最小なので、頂点 4 が確定。

　頂点 4 から 1 ステップで行ける頂点はないので、何もしない。

　確定していない頂点は、頂点 2 しかないので、頂点 2 が確定。

　全部確定したので終了。

結局ソースコードは？ (C++)

単純なやつ

\(O(|V|^2)\)

#include<bits/stdc++.h>

using namespace std;

class Dijkstra{
public:
	struct Edge{  // 辺 (コストあり)
		int to;  // 終点
		long long cost;  // コスト
		Edge(int to, long long cost):to(to),cost(cost){}
	};

private:
	const long long INF=1ll<<60;  // 無限 (最短距離としてあり得ない値)
	vector<vector<Edge>> g;  // 有向グラフ
	vector<long long> d;  // 距離
	vector<int> prev;  // 経路復元用
	int n; // 頂点数

public:
	Dijkstra(int v):g(v),d(v,INF),prev(v,-1),n(v){}  // 頂点数 v で初期化

	void edge(int from, int to, long long cost){  // [始点 from, 終点 to, コスト cost] の辺の追加 (無向グラフの場合は 2 方向の辺を追加してね)
		g[from].emplace_back(to,cost);
	}

	void solve(int s){  // スタート地点を s として、ダイクストラ法を実行
		bool c[n]={0}; // 最短距離と確定しているかどうか
		d[s]=0;  // スタート地点は最短距離 0
		c[s]=true; // スタート地点を最短距離と確定

		int v=s; // 新たに確定した頂点
		for(int i=1;i<n;i++){
			for(auto e:g[v]){  // 新たに確定した頂点からの辺がある頂点の距離を更新
				if(d[e.to]>d[v]+e.cost){  // 距離が短くなるなら
					d[e.to]=d[v]+e.cost;  // 距離を更新
					prev[e.to]=v;  // 1 つ前の経路を保存
				}
			}
			
			long long min=INF;  // 確定していない頂点の最小の距離を初期化
			for(int j=0;j<n;j++){  //  確定していない頂点のうち、距離が最小のものを調べる
				if(!c[j]){  //確定していない頂点なら
					if(min>d[j]){  //  現時点で調べた中で最小なら
						min=d[j];  //  最小値を更新
						v=j;  // 距離が最小の頂点を更新
					}
				}
			}
			if(min==INF)break;  // 確定していない頂点のうち、スタート地点からたどり着ける頂点がなければ終了
			c[v]=true;  // 確定していない頂点のうち、距離が最小のものを確定
		}
	}

	vector<long long>getD(){  // 最短距離を取得
		return d;
	}

	long long getD(int to){  // 頂点 to への最短距離を取得
		return d[to];
	}

	vector<int> getPath(int to){  // 頂点 to までの経路を取得
		vector<int> path;
		for(int cur=to;cur!=-1;cur=prev[cur])path.push_back(cur);
		reverse(path.begin(),path.end());
		return path;
	}
};

優先度付きキューを使ったやつ

\(O(|E|\log|E|)\)

#include<bits/stdc++.h>

using namespace std;

class Dijkstra{
public:
	struct Edge{  // 辺 (コストあり)
		int to;  // 終点
		long long cost;  // コスト
		Edge(int to, long long cost):to(to),cost(cost){}
	};

private:
	const long long INF=1ll<<60;  // 無限 (最短距離としてあり得ない値)
	vector<vector<Edge>> g;  // 有向グラフ
	vector<long long> d;  // 距離
	vector<int> prev;  // 経路復元用

public:
	Dijkstra(int v):g(v),d(v,INF),prev(v,-1){}  // 頂点数 v で初期化

	void edge(int from, int to, long long cost){  // [始点 from, 終点 to, コスト cost] の辺の追加 (無向グラフの場合は 2 方向の辺を追加してね)
		g[from].emplace_back(to,cost);
	}

	void solve(int s){  // スタート地点を s として、ダイクストラ法を実行
		priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq; // 優先度付きキュー (昇順)
		d[s]=0;  // スタート地点は距離 0
		pq.emplace(0,s);  // 距離を更新したらキューに挿入
		pair<long long,int> p;

		while(!pq.empty()){
			p=pq.top();
			pq.pop();
			if(d[p.second]<p.first)continue;  // 確定している頂点なら無視
			for(auto e:g[p.second]){  // 新たに確定した頂点からの辺がある頂点の距離を更新
				if(d[e.to]>d[p.second]+e.cost){  // 距離が短くなるなら更新
					d[e.to]=d[p.second]+e.cost;  // 距離の更新
					pq.emplace(d[e.to], e.to);  // 距離を更新したらキューに挿入
					prev[e.to]=p.second;  // 1 つ前の経路を保存
				}
			}
		}
	}

	vector<long long>getD(){  // 最短距離を取得
		return d;
	}

	long long getD(int to){  // 頂点 to への最短距離を取得
		return d[to];
	}

	vector<int> getPath(int to){  // 頂点 to までの経路を取得
		vector<int> path;
		for(int cur=to;cur!=-1;cur=prev[cur])path.push_back(cur);
		reverse(path.begin(),path.end());
		return path;
	}
};

ちゃんと値の更新をするタイプ (未作成)

\(O(|E|+|V|\log|V|)\)

(優先度付きキューがフィボナッチヒープだと、\(O(|E|+|V|\log|V|)\)、二分ヒープだと、最悪計算量が \(O((|E|+|V|)\log|V|)\) で、平均計算量が \(O(|E|+|V|\log\frac{|E|}{|V|}\log|V|)\) らしい。(Wikipedia))