最短経路への適用

演習
• 配列を用いてヒープ（優先度付き待ち行列）を実装せよ。
• とりあえず、insertとdeleteminを実装してみよう。
public class QueueTest {
static int[] a;
static int n; // 現在の要素数
static void insert(int v) {
a[n] = v;
for (int j = n; j>0 && a[j]<a[(j-1)/2]; j = (j-1)/2) {
int w = a[j]; a[j] = a[(j-1)/2]; a[(j-1)/2] = w;
}
n++;
}
static int deletemin() {
int m = a[0];
n--;
a[0] = a[n];
...
return m;
}
public void main(String[] args) {
a = new int[100];
n = 0;
insert(3); insert(2);
System.out.println(deletemin());
}
}
最短経路への適用
• 配列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) {
...
}

Download Report