概要
前回のダイクストラ法の記事の続編です。
優先度付きキューを用いて、計算量を減らします。
前回、愚直にダイクストラ法を実装した際の計算量は、O(V^2)でした（Vは頂点数）。
今回はダイクストラ法で毎回求める「確定していない頂点のうち最小の値（ある頂点からの最短距離）を持つ頂点」の探索に優先度付きキューを用いることで、計算量をO((E+V)logV)まで落とします。
優先度付きキューとは
wikipediaより。
優先度付きキュー（ゆうせんどつき -、英: priority queue）は、以下の4つの操作をサポートする抽象データ型である。
キューに対して要素を優先度付きで追加する。
最も高い優先度を持つ要素をキューから取り除き、それを返す。
(オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。
(オプション) 指定した要素を取り除くことなく優先度を変更する
ここで、Javaの優先度付きキューのクラスでは、要素の挿入と取り出しをO(logN)で行うことができます（Nはキューのサイズ）。線形時間より早いので単純に探索するより早いというわけです。
Javaのドキュメントを参照してPriorityQueueの実装
PriorityQueueのドキュメントを参照し、ちょっと試してみましょう。
よく使いそうなのが、addやpeek、pollメソッドです。
通常のQueueクラスと同じようなものですね。
addは要素の追加、peekは参照、pollは参照して削除です。
昇順
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.add(1);
q.add(2);
q.add(3);
q.add(4);
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
}
}
1
2
3
昇順(2)
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.add(4);
q.add(3);
q.add(2);
q.add(1);
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
}
}
1
2
3
確かに整数の昇順で優先度がついていそうです。
降順
降順にするには以下のように書きます。
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
q.add(1);
q.add(2);
q.add(3);
q.add(4);
System.out.println(q.poll());
System.out.println(q.poll());
System.out.println(q.poll());
}
}
4
3
2
自定義のクラス
自分で定義したクラスを優先度付きキューで管理したい場合は以下のように書きますね。
Comparableを実装してみました。
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<MyStr> q = new PriorityQueue<>();
q.add(new MyStr("d"));
q.add(new MyStr("c"));
q.add(new MyStr("b"));
q.add(new MyStr("a"));
System.out.println(q.poll().str);
System.out.println(q.poll().str);
System.out.println(q.poll().str);
}
}
class MyStr implements Comparable<MyStr> {
String str;
public MyStr(String s) {
this.str = s;
}
@Override
public int compareTo(MyStr myStr) {
return str.compareTo(myStr.str);
}
}
a
b
c
ダイクストラ法の実装
ちょっと遠回りしましたが、ダイクストラ法の実装をします。
例題は前回のダイクストラ法の記事と同じものを使用します。
問題はこちらのリンクです。
ちなみに前回の提出コードはこちらです。
これに優先度付きキューを用いて、より早くします。
ACコードは以下のとおりです。
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<ArrayList<Integer>> edge = new ArrayList<>(); // 頂点と接続している点
for (int i = 0; i < n; i++) {
edge.add(new ArrayList<>()); // 初期化
}
long[][] cost = new long[n][n]; // 2点間の距離
boolean[] used = new boolean[n]; // 確定したかどうか
long ans[] = new long[n]; // 頂点0からの最短距離
// 入力の受け取り
for (int i = 0; i < n; i++) {
int u = sc.nextInt(); // 頂点
int k = sc.nextInt(); // 頂点uからの出自数
for (int j = 0; j < k; j++) {
int v = sc.nextInt(); // uと隣接する頂点
long c = sc.nextInt(); // uとvの距離（重み）
edge.get(u).add(v); // uとvが隣接しているという情報を格納
cost[u][v] = c; // uからvへの距離（重み）を更新
}
}
// ここからダイクストラ
PriorityQueue<Node> q = new PriorityQueue<>(); // 優先度付きキューの宣言
/*
* 始点に0を設定する。（未確定。その他のノードには便宜的にINFなどを入れておくことが多い）
*/
for (int i = 0; i < n; i++) {
ans[i] = Long.MAX_VALUE;
}
ans[0] = 0;
q.add(new Node(0, 0)); // 優先度付きキューに未確定のキュー格納
for (;;) {
// 以下コメントアウト
// /*
// * 未確定のノードから、最短のものを一つ選択し、そこを確定させる。
// */
// long minDistance = Long.MAX_VALUE;
// int minTyoten = -1;
// for (int i = 0; i < n; i++) {
// if (!used[i]) {
// if (minDistance > ans[i]) {
// minDistance = ans[i];
// minTyoten = i;
// }
// }
// }
//
// /*
// * すべてのノードが確定していれば、終了。確定していなければ、最初に戻る
// */
// if (minDistance == Long.MAX_VALUE) {
// break;
// }
//
// // 頂点を確定させる。
// used[minTyoten] = true;
/*
* すべてのノードが確定していれば、終了。確定していなければ、最初に戻る
*/
if (q.size() == 0) {
break;
}
/*
* 未確定のノードから、最短のものを一つ選択し、そこを確定させる。
*/
Node node = q.poll(); // 現状最短のNode
int minTyoten = node.tyoten;
if (used[minTyoten]) {
continue;
}
used[minTyoten] = true;
/*
* 直前で確定したノードから直接つながっているノードに対して、かかる時間を計算する。
* そのノードが現状持っている最短経路より短ければ、その値で更新する。
*/
for (int next : edge.get(minTyoten)) {
if (ans[next] > ans[minTyoten] + cost[minTyoten][next]) {
ans[next] = ans[minTyoten] + cost[minTyoten][next];
q.add(new Node(next, ans[next]));
}
}
}
// 答えの出力
int i = 0;
for (long h : ans) {
System.out.println(i++ + " " + h);
}
}
}
class Node implements Comparable<Node> {
int tyoten;
long minDistance;
public Node(int t, long m) {
tyoten = t;
minDistance = m;
}
@Override
public int compareTo(Node o) {
int res = -1;
if (this.minDistance - o.minDistance >= 0) {
res = 1;
}
return res;
}
}
なにげにcompareToなどの実装が手間取りましたが、これでACしました。
計算量も減ったと思うので、またの機会にもうちょっと制約の厳しそうな問題にも挑戦してみたいと思います。
＃追記
costを行列で表している分まだ無駄なメモリを使ってしまっているようです。。
「隣接リスト」を用いると良いそうなのでまたの機会に実装してみます。
※「競技プログラミング研究月間 - みんなでさらなる高みを目指そう」が開催中のようです。