「グラフ(graph)」とは「節点(node)」または「頂点(vertex)」を 「辺(edge)」または「枝(branch)」で結んだものです。
グラフの例を図１に示します。 辺の上の数字は、ノード間の距離を表しています。
|
| 図1:グラフの例 |
図1のグラフは表1の隣接行列で表現できます。 ここで、行列の各要素は、ノード間が直接つながっている場合は「距離」に、 つながっていない場合は「-」になっています。 また、同一ノードの間の距離は0であるとしています。
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 表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"と出力しなさい。
ダイクストラ法とは、各ノードへの最短経路を、始点の周辺から１個所ずつ 確定し、徐々に範囲を広げていく方法です。
 |
出発地点を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)を選んで、その距離を その地点の最小距離として確定します。 これで全ての地点までの最短距離が確定しました。 |
| 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 |
次のグラフに関して、出発地点をa, 目的地点をiとしたときの、 最短経路の距離を答えなさい。
Dijkstra1.javaを次のデータに対して動作させて、計算時間を計測して下さい。
