アルゴリズム

ダイクストラ (Dijkstra) 法

グラフ

「グラフ(graph)」とは「ノード(節点、node)」を 「エッジ(辺、edge)」で結んだものです。 「ノード」は「頂点(vertex)」、「エッジ」は「枝(branch)」と呼ばれることもあります。

グラフの例を図１に示します。 図の中で「ノード」はアルファベットに丸で、「エッジ」はノードをつなぐ 線で表現されています。 エッジの上の数字は、エッジの重み(次の問題では「ノード間の距離」の意味になります)です。

図1:グラフの例

図1のグラフは表1の隣接行列で表現できます。 ここで、行列の各要素は、ノード間が直接つながっている場合は「距離」に、 つながっていない場合は「-」になっています。 また、同一ノードの間の距離は0であるとしています。

abcdefgh
a0172----
b10--24--
c7-0--23-
d2--0--5-
e-2--01--
f-42-10-6
g--35--02
h-----620
表1: 隣接行列

例題: 最短経路を求める

いくつかの都市と、それらの都市をつなぐ道路の距離が与えられている。 出発地点と目的地点が与えられたとき、最短経路を探すプログラムを 作りなさい。

入力形式

N R
A1 B1 L1
A2 B2 L2
...
AR BR LR
S D

最初の行には２個の整数 N と R が含まれる。 N は都市の数(ただし1≦N≦100)を表し、 Rはそれらの都市をつなぐ道の個数を表す。

２行目以降はR行に渡って、３個の整数 Ai, Bi, Li が含まれる(1≦i≦R)。 Ai と Biは道の両端の都市を表し (0≦Ai≦N-1, 0≦Bi≦N-1)、 Liは道の距離を表す(1≦Si≦1000)。

その次の行に２個の整数 S, D が含まれる。 S は出発地点の都市を表し、Dは目的地点の都市を表す (0≦S≦N-1, 0≦D≦N-1)。

出力

答が発見された場合は次のように出力しなさい。

最初の行に「最短経路の距離」を表す整数を出力し、 次の行に「 最短経路を辿ったときの都市を、出発地点から 目的地点まで順にスペースを１個ずつあけて」出力しなさい。

最短経路が複数ある場合は、そのうちの１つの経路を答えとすればよい ものとする。

答えが無い場合は、"No route"と出力しなさい。

ダイクストラ法

ダイクストラ法とは、各ノードへの最短経路を、始点の周辺から１個所ずつ 確定し、徐々に範囲を広げていく方法です。

  1. 各地点までの距離を未確定とし、とりあえず無限大としておきます。
  2. 始点の距離を0とおきます。
  3. 未確定の地点の中から、距離が最も小さい地点を選んで、 その距離を「その地点までの最短距離」として確定します。
  4. 今確定した地点から「直接つながっている」かつ 「未確定である」地点に対して、今確定した場所を経由した場合の 距離を計算し、今までの距離よりも小さければ書き直します。
  5. 全ての地点が確定すれば終了です。そうでなければ3へ。
出発地点をa、目的地点hとして、最短経路を通った場合の距離を求めましょう。
全ての地点までの距離を未確定とし、とりあえず無限大としておきます。その上で、出発地点(a)までの距離を0とします。
未確定の中から距離が最も小さい地点(a)を選んで、その距離を その地点の最小距離として確定します （確定した場所は、赤い曲線で囲んで表しています。 今確定した場所は☆印をつけて表しています。）
今確定した場所（☆印がついている場所, a）から「直接つながっている」 かつ「未確定の」地点(b,c,d)に関して、今確定した場所(a)を経由した場合の距離を 計算し、今までの距離よりも小さければ書き直します。 (b,c,dがそれぞれ∞から1,7,2に書き替りました)。
未確定の中から距離が最も小さい地点(b)を選んで、その距離を その地点の最小距離として確定します。 もし、最小値を持つ地点が複数ある場合は、そのなかのどれを 選んでも構いません。 今確定した場所(b)を☆印をつけて表しています。
今確定した場所（☆印がついている場所, b）から「直接つながっている」 かつ「未確定の」地点(e,f)に関して、今確定した場所(b)を経由した場合の距離を 計算し、今までの距離よりも小さければ書き直します。 (e,fがそれぞれ3,5に書き替りました)。
未確定の中から距離が最も小さい地点(d)を選んで、その距離を その地点の最小距離として確定します。
今確定した場所（☆印がついている場所, d）から「直接つながっている」 かつ「未確定の」地点(g)に関して、今確定した場所を経由した場合の距離を計算し、 今までの距離よりも小さければ書き直します。 (gが7に書き替りました)。
未確定の中から距離が最も小さい地点(e)を選んで、その距離を その地点の最小距離として確定します。
今確定した場所（☆印がついている場所, e）から「直接つながっている」 かつ「未確定の」地点(f)に関して、今確定した場所を経由した場合の距離を計算し、 今までの距離よりも小さければ書き直します。 (fが4に書き替りました)。
未確定の中から距離が最も小さい地点(f)を選んで、その距離を その地点の最小距離として確定します。
今確定した場所（☆印がついている場所, f）から「直接つながっている」 かつ「未確定の」地点(c,h)に関して、今確定した場所を経由した場合の距離を計算し、 今までの距離よりも小さければ書き直します。 (c,hがそれぞれ6,10に書き替りました)。
未確定の中から距離が最も小さい地点(c)を選んで、その距離を その地点の最小距離として確定します。
今確定した場所（☆印がついている場所, c）から「直接つながっている」 かつ「未確定の」地点(g)に関して、今確定した場所を経由した場合の距離を計算し、 今までの距離よりも小さければ書き直します。 (gは書き替りませんでした)。
未確定の中から距離が最も小さい地点(g)を選んで、その距離を その地点の最小距離として確定します。
今確定した場所（☆印がついている場所, g）から「直接つながっている」 かつ「未確定の」地点(h)に関して、今確定した場所を経由した場合の距離を計算し、 今までの距離よりも小さければ書き直します。 (hは9に書き替りました)。
未確定の中から距離が最も小さい地点(h)を選んで、その距離を その地点の最小距離として確定します。 これで全ての地点までの最短距離が確定しました。

ダイクストラ法が正しく動作する理由

ダイクストラ法で、最短距離が正しく求まる理由を説明します。


具体例で考えます。上図は「ノード a, b への最短距離が求まった」状態です。 赤い境界線の左側のノード a, bが「すでに最短距離が確定したノード」で、 右側のノード c, d, e, f, g, h が「まだ最短距離が未確定なノード」です。

ダイクストラ法は、 この状況で「未確定なノードのうちで最小の値を持つノード d への最短距離を現在の推定値 (= 2) で確定してよい」ことを主張します。 そして、その主張が正しいことは「ダイクストラ法が対象にしているグラフはエッジの重みが 0 以上」であることから明らかです。 理由を以下で説明します。

「未確定なノード」 c, d, e, f, g, h は、現在の推定値が 「無限大でないノード」 c, d, e と 「無限大のノード」 f, g, h の2種類に分けることができます。 そのうち、「無限大のノード」 f, g, h は「確定したノード」 a, b との間に直接のエッジがないので 「無限大でないノード」c, d, e のどれかを経由しなければ始点から到達できず、 その経由ノードよりも最短距離が小さくなることはありません。

「無限大でないノード」 c, d, e の中で推定値が最小のノード d は、 「未確定なノード」全体の中でも最短距離が最小となります。 始点からノード d に到達するのに、 既にノード d 以上の値を持つ他の「未確定なノード」 c, e などを経由すると、 必ず現在の d の値以上の距離になってしまうからです。 なぜなら、エッジの重みは 0 以上の値ですから。

つまり、始点からノード d への最短距離は現時点で正しく推定されており、 現在の値で確定してよいのです。

このように考えると、ダイクストラ法はごくごく当たり前のことを主張していることがわかります。

ダイクストラ法のプログラム (Pyton 3)

dijkstra.py
#!/usr/bin/env python
import queue

G = [{}]

def setNode(n):
  global G
  G = [{} for i in range(n)]
def addEdge(s,t,w):
  global G
  G[s][t]=w
def solve(s,t):
  global G
  fixed = {}
  q = queue.PriorityQueue()
  q.put((0,s))
  while q.empty() == False:
    w,x = q.get()
    if x == t: return w
    if x in fixed: continue;
    fixed[x] = w
    for y in G[x]:
      if (y in fixed) == False:
        q.put((w + G[x][y], y))
  return None


n,m = map(int,input().split())
setNode(n)
for i in range(m):
  s,t,w = map(int,input().split())
  G[s][t] = w
  G[t][s] = w
src, dst = map(int,input().split())
print(solve(src,dst))
dijkstra.pyの実行例
$ javac Dijkstra.java
$ java Dijkstra <route03.data
distance=213

ダイクストラ法のプログラム (java, 遅いバージョン )

Java で、敢えて愚直に書いた遅いプログラムは次のようになります。

Dijkstra.java
import java.util.Scanner;	// java1.5で入力を扱うクラス
public class Dijkstra {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in); // 標準入力から読む
	int nTown = sc.nextInt(); // 都市の数
	int nRoute = sc.nextInt(); // 道路の数
	int[][] map = new int[nTown][nTown]; // 都市の接続関係のマップ
	for (int i=0; i<nTown; i++) // 接続マップを初期化する
	    for (int j=0; j<nTown; j++)
		map[i][j] = (i==j) ? 0 : -1;
	for (int i=0; i<nRoute; i++) { // 道路の状況を読み込む
	    int from = sc.nextInt();
	    int to = sc.nextInt();
	    int len = sc.nextInt();
	    map[from][to] = map[to][from] = len;
	}
	int src = sc.nextInt();	// 出発地点
	int dst = sc.nextInt();	// 到着地点
	int[] distance = new int[nTown]; // 各都市までの最短距離
	dijkstra(map,src,distance);
	if (distance[dst]==Integer.MAX_VALUE) {	// 解なし
	    System.out.println("no route");
	} else {
	    System.out.println("distance="+distance[dst]);
	}
    }
    public static void dijkstra(int[][] map,int src,int[] distance) {
	int nTown = distance.length;
	boolean[] fixed = new boolean[nTown]; // 最短距離が確定したかどうか
	for (int i=0; i<nTown; i++) { // 各都市について初期化する
	    distance[i] = Integer.MAX_VALUE; // 最短距離の初期値は無限遠
	    fixed[i] = false;	// 最短距離はまだ確定していない
	}
	distance[src] = 0;	// 出発地点までの距離を0とする
	while (true) {
	    // 未確定の中で最も近い都市を求める
	    int marked = minIndex(distance,fixed);
	    if (marked < 0) return; // 全都市が確定した場合
	    if (distance[marked]==Integer.MAX_VALUE) return; // 非連結グラフ
	    fixed[marked] = true; // その都市までの最短距離は確定となる
	    for (int j=0; j<nTown; j++) { // 隣の都市(i)について
		if (map[marked][j]>0 && !fixed[j]) { // 未確定ならば
		    // 旗の都市を経由した距離を求める
		    int newDistance = distance[marked]+map[marked][j];
		    // 今までの距離よりも小さければ、それを覚える
		    if (newDistance < distance[j]) distance[j] = newDistance;
		}
	    }
	}
    }
    // まだ距離が確定していない都市の中で、もっとも近いものを探す
    static int minIndex(int[] distance,boolean[] fixed) {
	int idx=0;
	for (; idx<fixed.length; idx++)	// 未確定の都市をどれか一つ探す
	    if (!fixed[idx]) break;
	if (idx == fixed.length) return -1; // 未確定の都市が存在しなければ-1
	for (int i=idx+1; i<fixed.length; i++) // 距離が小さいものを探す
	    if (!fixed[i] && distance[i]<distance[idx]) idx=i;
	return idx;
    }
}
Dijkstra.javaの実行例
$ javac Dijkstra.java
$ java Dijkstra <route03.data
distance=213

最短経路の表示

最短経路を表示するように変更してみましょう。

各地点の距離を更新するときに、どの地点を直前に経由したのかを 記録するようにします。

Dijkstra1.javaの変更点
*** java/Dijkstra.java	Sat Dec 17 17:09:42 2005
--- java/Dijkstra1.java	Sat Dec 17 17:09:42 2005
***************
*** 1,5 ****
  import java.util.Scanner;	// java1.5で入力を扱うクラス
! public class Dijkstra {
      public static void main(String[] args) {
  	Scanner sc = new Scanner(System.in); // 標準入力から読む
  	int nTown = sc.nextInt(); // 都市の数
--- 1,5 ----
  import java.util.Scanner;	// java1.5で入力を扱うクラス
! public class Dijkstra1 {
      public static void main(String[] args) {
  	Scanner sc = new Scanner(System.in); // 標準入力から読む
  	int nTown = sc.nextInt(); // 都市の数
***************
*** 17,35 ****
  	int src = sc.nextInt();	// 出発地点
  	int dst = sc.nextInt();	// 到着地点
  	int[] distance = new int[nTown]; // 各都市までの最短距離
! 	dijkstra(map,src,distance);
  	if (distance[dst]==Integer.MAX_VALUE) {	// 解なし
  	    System.out.println("no route");
  	} else {
  	    System.out.println("distance="+distance[dst]);
  	}
      }
!     public static void dijkstra(int[][] map,int src,int[] distance) {
  	int nTown = distance.length;
  	boolean[] fixed = new boolean[nTown]; // 最短距離が確定したかどうか
  	for (int i=0; i<nTown; i++) { // 各都市について初期化する
  	    distance[i] = Integer.MAX_VALUE; // 最短距離の初期値は無限遠
  	    fixed[i] = false;	// 最短距離はまだ確定していない
  	}
  	distance[src] = 0;	// 出発地点までの距離を0とする
  	while (true) {
--- 17,40 ----
  	int src = sc.nextInt();	// 出発地点
  	int dst = sc.nextInt();	// 到着地点
  	int[] distance = new int[nTown]; // 各都市までの最短距離
! 	int[] via = new int[nTown]; // 経由地
! 	dijkstra(map,src,distance,via);
  	if (distance[dst]==Integer.MAX_VALUE) {	// 解なし
  	    System.out.println("no route");
  	} else {
  	    System.out.println("distance="+distance[dst]);
+ 	    for (int i=dst; i!=src; i=via[i])
+ 		System.out.print(i + " ");
+ 	    System.out.println(src);
  	}
      }
!     public static void dijkstra(int[][] map,int src,int[] distance,int[] via) {
  	int nTown = distance.length;
  	boolean[] fixed = new boolean[nTown]; // 最短距離が確定したかどうか
  	for (int i=0; i<nTown; i++) { // 各都市について初期化する
  	    distance[i] = Integer.MAX_VALUE; // 最短距離の初期値は無限遠
  	    fixed[i] = false;	// 最短距離はまだ確定していない
+ 	    via[i] = -1;	// 最短経路の経由地は決っていない
  	}
  	distance[src] = 0;	// 出発地点までの距離を0とする
  	while (true) {
***************
*** 43,49 ****
  		    // 旗の都市を経由した距離を求める
  		    int newDistance = distance[marked]+map[marked][j];
  		    // 今までの距離よりも小さければ、それを覚える
! 		    if (newDistance < distance[j]) distance[j] = newDistance;
  		}
  	    }
  	}
--- 48,57 ----
  		    // 旗の都市を経由した距離を求める
  		    int newDistance = distance[marked]+map[marked][j];
  		    // 今までの距離よりも小さければ、それを覚える
! 		    if (newDistance < distance[j]) {
! 			distance[j] = newDistance;
! 			via[j] = marked; // 経由地を書き換える
! 		    }
  		}
  	    }
  	}
Dijkstra1.javaの実行例
$ javac Dijkstra1.java
$ java Dijkstra1 <route03.data
distance=213
29 25 24 20 15 10 5 4 0

課題1

次のグラフに関して、出発地点をa, 目的地点をiとしたときの、 最短経路の距離を答えなさい。

課題2

Dijkstra1.javaを次のデータに対して動作させて、計算時間を計測して下さい。

Priority First Search (java)

ダイクストラ法において、疎なグラフ(つまりノード数に比べて エッジの数が少ないグラフ)を扱う場合には、

という工夫をすることによって、実際の計算速度が速くなることが期待されます (計算量のオーダーは変わりませんが)。 このアルゴリズムは「ダイクストラ法」ですが、 「Priority First Search (順位優先探索)」 と呼ばれることがあります。

Priority Queueは「ヒープ」と呼ばれる、 「特定のデータへのアクセスがO(log n)で可能」 なデータ構造です。

JavaではPriorityQueueクラスが標準ライブラリにありますので、 これを使ってPriority First Searchを記述してみましょう。

Node.java
import java.util.*;
public class Node implements Comparable {
    int id;
    double value;
    Node via;
    Vector<Edge> edges;
    public Node(int id) {
	this.id = id;
	this.value = Double.MAX_VALUE;
	this.via = null;
	this.edges = new Vector<Edge>();
    }
    public int compareTo(Object o) {
	if (! (o instanceof Node)) throw new IllegalArgumentException("Node needed");
	Node x = (Node)o;
	return (this.value > x.value)? 1 :
	    ((this.value < x.value)? (-1) : 0);
    }
    public String toString() {
	return "node#"+id+"["+((via==null)? "null":via.id)+","+value+"]";
    }
    public static String toString(Node[] a) {
	StringBuffer sb = new StringBuffer();
	sb.append("[");
	for (int i=0; i<a.length; i++) sb.append(((i==0)?"":" ")+a[i]);
	sb.append("]");
	return sb.toString();
    }
}
Edge.java
import java.util.*;
public class Edge {
    Node src;
    Node dst;
    double value;
    public Edge(Node src,Node dst,double value) {
	this.src = src;
	this.dst = dst;
	this.value = value;
    }
    public String toString() {
	return "edge#"+value+"("+src+","+dst+")";
    }
    public static String toString(Vector<Edge> v) {
	return toString(v.toArray(new Edge[0]));
    }
    public static String toString(Edge[] a) {
	StringBuffer sb = new StringBuffer();
	sb.append("[");
	for (int i=0; i<a.length; i++) sb.append(a[i] + " ");
	sb.append("]");
	return sb.toString();
    }
}
PFSearch.java
import java.util.*;
public class PFSearch {
    Node[] nodes;
    public PFSearch(Node[] nodes) {
	this.nodes = nodes;
    }
    public void solve(Node src,Node dst) {
	// 未確定のノードを優先度キューで管理する
	PriorityQueue<Node> q = new PriorityQueue<Node>();
	// まず、全てのノードを未確定のノードとする。
	for (int i=0; i<nodes.length; i++) {
	    nodes[i].value = Double.MAX_VALUE;	// 距離の初期値は無限大
	    q.add(nodes[i]);
	}
	// 始点ノードの距離を0と設定して、未確定ノード群に入れる。
	q.remove(src);	// 未確定ノード群から始点ノードを一旦取り出して
	src.value = 0;	// 距離を0に書き換えて
	q.offer(src);	// 未確定ノード群に戻す
	while (q.size() > 0) {	// 未確定ノード群にノードがある限り繰り返す
	    Node x = q.poll();	// 距離最小ノードを未確定ノード群から取り出す
	    if (x.value == Double.MAX_VALUE) return; // 非連結ノード
	    if (x == dst) return; // 目的地までの距離が確定したら終了する
	    // 取り出したノードに隣接するノードの距離を書き換える
	    for (Iterator<Edge> it=x.edges.iterator(); it.hasNext(); ) {
		Edge e = it.next(); // xにつながっているエッジ
		Node y = e.dst; // xに隣接しているノードをyとする
		double newValue = x.value +e.value; // x経由でのyまでの距離
		if (newValue < y.value) { // 新しい経路の方が近ければ
		    if (q.remove(y)) { // 可能ならば未確定ノード群から取り除き
			y.value = newValue; // yの距離を変更してから
			y.via = x; // x経由と記録して
			q.offer(y);	// yを未確定ノード群に戻す
		    }
		}
	    }
	}
    }
    public Node[] getPath(int id) {
	Vector<Node> v = new Vector<Node>();
	for (Node node = nodes[id]; node != null; node=node.via) v.add(node);
	for (int i=0; i<v.size()/2; i++) { // 逆順なので順番を逆に戻す
	    int j=v.size()-1-i;
	    Node tmp=v.get(i);
	    v.set(i,v.get(j));
	    v.set(j,tmp);
	}
	return v.toArray(new Node[0]); // 配列に変換して返す
    }
    public String toString() {
	return Node.toString(nodes);
    }
}
RunPFSearch.java
import java.util.*;
public class RunPFSearch {
    static Node[] nodes;
    static int src;
    static int dst;
    public static void main(String[] args) {
	doInput();
	PFSearch dj = new PFSearch(nodes);
	dj.solve(nodes[src],nodes[dst]);
	System.out.println(dj.nodes[dst]);
	// System.out.println(Node.toString(dj.getPath(dst)));
    }
    static void doInput() {
	Scanner sc = new Scanner(System.in);
	int nTown = sc.nextInt(); // 都市の数
	int nRoute = sc.nextInt(); // 道路の数

	nodes = new Node[nTown];
	for (int i=0; i<nTown; i++) nodes[i] = new Node(i);
	for (int i=0; i<nRoute; i++) {
	    int from = sc.nextInt();
	    int to = sc.nextInt();
	    double len = sc.nextDouble();
	    nodes[from].edges.add(new Edge(nodes[from],nodes[to],len));
	    nodes[to].edges.add(new Edge(nodes[to],nodes[from],len));
	}
	src = sc.nextInt();	// 出発地点
	dst = sc.nextInt();	// 到着地点
    }
}

ノードの数が多い疎なグラフを表すデータ、たとえば routedata12.txt に対して、RunPFSearch.java を実行してみましょう。 現実的な時間で答が得られるはずです。

routedata12.txt(一部)
19500 39126
0 1 5
0 150 8
1 2 9
1 151 1
2 3 4
...(略)...

注意

グラフ中に負の重みのエッジが存在する場合はダイクストラ法では解けません。 そのような場合はBellman-Ford法を使って解きます。
Yoshihisa Nitta

http://nw.tsuda.ac.jp/