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

最短経路 最短経路 有向グラフの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); } } 配列の配列 配列の配列は次のように宣言?生成する。 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}; 最短経路（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に加える; } } public class Dijkstra { static int[][] edges = ...; static int[][] lengths = ...; static int n = edges.length;