最短経路（Dijkstra法） - lecture.ecc.u

最短経路
最短経路
• 有向グラフのstart点から与えられたgoal点までの最
短の経路を求める。ここでは、各辺の長さは１とする。
• 点の数はn。各点は0～n-1の番号で参照。
for (int i = 0; i < n; i++) step[i] = -1;
step[start] = 0;
for (int s = 0; step[goal] == -1; s++)
for (step[i]==sを満たす各iについて)
for (iと隣接する各kについて)
if (step[k] == -1) {
step[k] = s+1;
prev[k] = i;
}
public class Node() {
int value;
Node next;
public Node(int x, Node n) {
value = x; next = n;
}
}
public class Shortest {
static int[][] edges = ...;
static int n = edges.length;
static int[] step = new int[n];
static int[] prev = new int[n];
static Node q0, q1;
static void shortest(int start, int goal) {
for (int i = 0; i < n; i++) step[i] = -1;
step[start] = 0; q0 = new Node(start, null);
for (int s = 0; step[goal] == -1; s++) {
while (q0 != null) {
int i = q0.value; int[] e = edges[i];
for (int j = 0; j < e.length; j++) {
int k = e[j];
if (step[k] == -1) {
step[k] = s+1;
q1 = new Node(k, q1);
prev[k] = i;
}
}
q0 = q0.next;
}
q0 = q1;
}
}
public static void main(String[] args) {
shortest(0, 9);
for (int i = 9; i != 0; i = prev[i])
System.out.println(i);
}
}
3
4
0
2
5
1
7
9
6
8
static int[][] edges = {
{1,2,3},
{6},
{4,5,6},
{2},
{7},
{9},
{9},
{8,9},
{7,9},
{}};
3
4
s=0
0
2
5
1
7
9
6
8
3
4
s=1
0
2
5
1
7
9
6
8
3
4
s=2
0
2
5
1
7
9
6
8
3
4
s=3
0
2
5
1
7
9
6
8
配列の配列
• 配列の配列は次のように宣言・生成する。
int[][] a = new int[5][3];
• 個々のa[i]は配列である。
int[] b;
b = a[3];
• 従って、各要素はa[i][j]
と参照する。
配列の配列（続き）
• 個々のa[i]は空（null）でもよい。
int[][] a = new int[5][];
• 個々のa[i]には、
大きさの異なる配列も
設定できる。
a[1] = new int[3];
a[2] = new int[2];
配列の配列（最後）
• 配列は生成時に初期化できる。
int[][] a = {null, {1,2,3}, {4,5}, null, null};
1
2
4
5
3
最短経路（Dijkstra法）
Dijkstra法
• 有向グラフのstart点からgoal点までの最短の経路を求める。
• 点の数はn。各点は0～n-1の番号で参照。
for (int i = 0; i < n; i++) dist[i] = ∞;
dist[start] = 0; pool = startのみからなる集合;
while (true) {
poolの中でdist[i]が最小のものをiとする;
poolからiを除く;
if (i == goal) break;
for (iと隣接する各kについて)
if (dist[i] + (iからkへの距離) < dist[k]) {
dist[k] = dist[i] + (iからkへの距離):
prev[k] = i; kをpoolに加える;
}
}
ここで停止しなけ
れば、start点から
任意の点までの最
短経路が求まる。
その場合、ループ
の条件を
while (pool != 空)
とする。
public class Dijkstra {
static int[][] edges = ...;
static int[][] lengths = ...;
static int n = edges.length;
static int[] dist = new int[n];
static int[] prev = new int[n];
static ... pool;
static void shortest(int start, int goal) {
for (int i = 0; i < n; i++) dist[i] = 999999;
dist[start] = 0; pool = startのみからなる集合;
while (true) {
int i = poolの中でdist[i]が最小のもの;
poolからiを除く;
if (i == goal) break;
int[] e = edges[i];
for (int j = 0; j < e.length; j++) {
int k = e[j];
if (dist[i] + lengths[i][j] < dist[k]) {
dist[k] = dist[i] + lengths[i][j];
prev[k] = i; poolにkを追加;
}
}
}
}
static int poolsize = 0;
static int[] poolarray = ...
poolを配列で実装する場合
static void shortest(int start, int goal) {
for (int i = 0; i < n; i++) dist[i] = 999999;
dist[start] = 0; poolarray[0] = start; poolsize = 1;
while (true) {
int i; int m = 999999;
for (int p = 0; p < poolsize; p++)
if (dist[poolarray[p]] < m) { i = p; m = dist[poolarray[p]]; }
poolからiを除く;
if (i == goal) break;
int[] e = edges[i];
for (int j = 0; j < e.length; j++) {
int k = e[j];
if (dist[i] + lengths[i][j] < dist[k]) {
dist[k] = dist[i] + lengths[i][j];
prev[k] = i;
for (int p = 0; p < poolsize; p++)
if (poolarray[p] == k) { k = -1; break; }
if (k >= 0) { poolarray[poolsize] = k; poolsize++; }
}
}
}
}
public static void main(String[] args) {
shortest(0, 9);
for (int i = 9; i != 0; i = prev[i])
System.out.println(i);
}
}
static int[][] edges = {
{1,2,3},
{6},
{4,5,6},
{2},
{7},
{9},
{9},
{8,9},
{7,9},
{}};
3
2
1
0
4
3
4
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
static int[][] lengths = {
{3,4,2},
{3},
{3,3,8},
{1},
{6},
{3},
{4},
{5,4},
{5,3},
{}};
3
pool:
2
1
0
4
3
4
0 (0)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
3 (2)
1 (3)
2 (4)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
2 (3)
1 (3)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
1 (3)
5 (6)
4 (6)
6 (11)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
6 (6)
5 (6)
4 (6)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
5 (6)
4 (6)
9 (10)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
4 (6)
9 (9)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
3
pool:
2
1
0
4
3
4
9 (9)
7 (12)
2
3
3
5
8
1
6
3
3
4
7
9
6
4
5
5
3
8
計算量
• いったんpoolから除かれた点は、
二度とpoolには入らない（辺の長さが非負ならば）。
• 内側のループは辺の数mだけ回る。
– 外側は点の数nだけ回るが、通常はm>nなので無視。
• poolの各操作が点の数nに比例するならば、O(mn)。
– 例えば、リストによってpoolを実装した場合。
– ヒープと呼ばれるデータ構造を用いると、
各操作をlog nに比例した時間で処理可能。
全体の計算量は、O(m log n)となる。
– さらにフィボナッチ・ヒープと呼ばれるデータ構造を
用いると、全体の計算量は、O(m+n log n)となる。
ヒープの適用
• 配列aに挿入するのは、グラフの点の番号。
• 比較は、distを参照して行えばよい。
a[j]<a[j/2-1]  dist[a[j]]<dist[a[j/2-1]]
ヒープの適用
• decrease_keyを行うためには、グラフの各点に対して、
ヒープの配列aの要素で、その点が入っている要素の
インデックスを対応させる配列を
用意しなければならない。
int[] index;
• index[v]は点vが入っているaの要素のインデックス。
– index[v]がiに等しいならば、a[i]はvに等しい。
• この配列の要素は-1で初期化してやる。
– vがヒープから除かれるとindex[v]は-1にもどる。
– index[v]が-1に等しければ、ヒープにないということ。
ヒープの適用
• insertはindexも変更する必要があるので以下のようになる。
static void insert(int v) {
a[n] = v;
index[v] = n;
for (int j = n; j>0 && dist[a[j]]<dist[a[(j-1)/2]];
j = (j-1)/2) {
int w = a[j]; a[j] = a[(j-1)/2]; a[(j-1)/2] = w;
index[a[j]] = j;
index[a[(j-1)/2] = (j-1)/2;
}
n++;
}
ヒープの適用
• distが優先度を保持しているので、
decrease_keyはグラフの点のみを
引数とすればよい。
（もちろん、distを変更してから呼ぶ。）
static void decrease_key(int v) {
...
}
二次元グラフィクス
import java.awt.*;
import javax.swing.*;
class GraphPanel extends JPanel {
int[][] edges;
int[] x;
int[] y;
int[] prev;
int start;
int goal;
GraphPanel(int[][] edges, int[] x, int[] y,
int[] prev, int start, int goal) {
this.edges = edges;
this.x = x;
this.y = y;
this.prev = prev;
this.start = start;
this.goal = goal;
setBackground(Color.white);
setMinimumSize(new Dimension(900, 500));
setPreferredSize(new Dimension(900, 500));
}
public void paintComponent(Graphics g){
super.paintComponent(g);
g.setColor(Color.BLACK);
for (int i = 0; i < edges.length; i++)
for (int j = 0; j < edges[i].length; j++) {
g.drawLine(x[i], y[i],
x[edges[i][j]], y[edges[i][j]]);
}
if (prev != null) {
g.setColor(Color.RED);
for (int i = goal; i != start; i = prev[i]) {
g.drawLine(x[i], y[i],
x[prev[i]], y[prev[i]]);
}
}
}
public static void main(String[] args) {
N01_07L_13.init();
JFrame f = new JFrame("Draw Example");
GraphPanel example =
new GraphPanel(N01_07L_13.edges,
N01_07L_13.x, N01_07L_13.y,
null, 0, 0);
f.getContentPane().add(example,
BorderLayout.CENTER);
f.pack();
f.setVisible(true);
}
}
演習
• GraphPanel.javaおよびN01_07L_13.javaを
コンパイルして、GraphPanel.mainを実行
してみよ。
Dijkstraのプログラムへの組み込み
• 例えば、mainを次のようにする。
public static void main(String[] args) {
N01_07L_13.init();
edges = N01_07L_13.edges;
lengths = N01_07L_13.lengths;
x = N01_07L_13.x;
y = N01_07L_13.y;
n = edges.length;
dist = new int[n];
prev = new int[n];
shortest(100, 1500);
JFrame f = new JFrame("Draw Example");
GraphPanel example =
new GraphPanel(edges, x, y, prev, 100, 1500);
f.getContentPane().add(example, BorderLayout.CENTER);
f.pack();
f.setVisible(true);
}
注意
• N01_07L_13において、任意の２点間が
連結であるとは限らない。

Download Report