最短経路.

Presentation on theme: "最短経路."— Presentation transcript:

1 最短経路

2 最短経路 有向グラフの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; }

3 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;

4 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;

5 public static void main(String[] args) {
shortest(0, 9); for (int i = 9; i != 0; i = prev[i]) System.out.println(i); }

6 static int[][] edges = { {1,2,3}, {6}, {4,5,6}, {2}, {7}, {9}, {8,9},
{7,9}, {}}; 3 4 2 5 1 7 9 6 8

7 3 4 s = 0 2 5 1 7 9 6 8

8 3 4 s = 1 2 5 1 7 9 6 8

9 3 4 s = 2 2 5 1 7 9 6 8

10 3 4 s = 3 2 5 1 7 9 6 8

11 配列の配列 配列の配列は次のように宣言・生成する。 int[][] a = new int[5][3]; 個々のa[i]は配列である。
int[] b; b = a[3]; 従って、各要素はa[i][j] と参照する。

12 配列の配列（続き） 個々のa[i]は空（null）でもよい。 int[][] a = new int[5][]; 個々のa[i]には、
大きさの異なる配列も 設定できる。 a[1] = new int[3]; a[2] = new int[2];

13 配列の配列（最後） 配列は生成時に初期化できる。
int[][] a = {null, {1,2,3}, {4,5}, null, null}; 1 2 3 4 5

14 最短経路（Dijkstra法）

15 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 != 空) とする。

16 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;

17 static void shortest(int start, int goal) {
for (int i = 0; i < n; i++) dist[i] = ; 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を追加; }

18 poolを配列で実装する場合 static int poolsize = 0; static int[] poolarray = ...
static void shortest(int start, int goal) { for (int i = 0; i < n; i++) dist[i] = ; dist[start] = 0; poolarray[0] = start; poolsize = 1; while (true) { int i; int m = ; 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; if (poolarray[p] == k) { k = -1; break; } if (k >= 0) { poolarray[poolsize] = k; poolsize++; } }

19 public static void main(String[] args) {
shortest(0, 9); for (int i = 9; i != 0; i = prev[i]) System.out.println(i); }

20 2 1 3 4 3 3 6 8 3 3 4 4 5 5 3 static int[][] edges = { {1,2,3}, 3 {6},
{4,5,6}, {2}, {7}, {9}, {8,9}, {7,9}, {}}; 3 2 1 4 3 4 2 3 3 6 5 1 8 static int[][] lengths = { {3,4,2}, {3}, {3,3,8}, {1}, {6}, {4}, {5,4}, {5,3}, {}}; 3 3 7 4 9 6 4 5 5 3 8

21 3 pool: 2 1 4 3 4 0 (0) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

22 3 pool: 2 1 4 3 4 3 (2) 1 (3) 2 (4) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

23 3 pool: 2 1 4 3 4 2 (3) 1 (3) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

24 3 pool: 2 1 4 3 4 1 (3) 5 (6) 4 (6) 6 (11) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

25 3 pool: 2 1 4 3 4 6 (6) 5 (6) 4 (6) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

26 3 pool: 2 1 4 3 4 5 (6) 4 (6) 9 (10) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

27 3 pool: 2 1 4 3 4 4 (6) 9 (9) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

28 3 pool: 2 1 4 3 4 9 (9) 7 (12) 2 3 3 6 5 1 8 3 3 7 4 9 6 4 5 5 3 8

29 計算量 いったんpoolから除かれた点は、 二度とpoolには入らない（辺の長さが非負ならば）。 内側のループは辺の数mだけ回る。
外側は点の数nだけ回るが、通常はm>nなので無視。 poolの各操作が点の数nに比例するならば、O(mn)。 例えば、リストによってpoolを実装した場合。 ヒープと呼ばれるデータ構造を用いると、 各操作をlog nに比例した時間で処理可能。 全体の計算量は、O(m log n)となる。 さらにフィボナッチ・ヒープと呼ばれるデータ構造を 用いると、全体の計算量は、O(m+n log n)となる。

30 ヒープの適用 配列aに挿入するのは、グラフの点の番号。 比較は、distを参照して行えばよい。
a[j]<a[j/2-1]  dist[a[j]]<dist[a[j/2-1]]

31 ヒープの適用 decrease_keyを行うためには、グラフの各点に対して、 ヒープの配列aの要素で、その点が入っている要素の
インデックスを対応させる配列を 用意しなければならない。 int[] index; index[v]は点vが入っているaの要素のインデックス。 index[v]がiに等しいならば、a[i]はvに等しい。 この配列の要素は-1で初期化してやる。 vがヒープから除かれるとindex[v]は-1にもどる。 index[v]が-1に等しければ、ヒープにないということ。

32 ヒープの適用 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++;

33 ヒープの適用 distが優先度を保持しているので、 decrease_keyはグラフの点のみを 引数とすればよい。
static void decrease_key(int v) { ... }

34 二次元グラフィクス import java.awt.*; import javax.swing.*;
class GraphPanel extends JPanel { int[][] edges; int[] x; int[] y; int[] prev; int start; int goal;

35 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)); }

36 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]) { 　　　x[prev[i]], y[prev[i]]);

37 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); }

38 演習 GraphPanel.javaおよびN01_07L_13.javaを コンパイルして、GraphPanel.mainを実行 してみよ。

39 Dijkstraのプログラムへの組み込み
例えば、mainを次のようにする。

40 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); }

41 注意 N01_07L_13において、任意の２点間が 連結であるとは限らない。