皆様はじめまして。@samba_glassと申します。
私は5年ほど前、C++で競技プログラミングを少しだけやっていましたが、長らく休止していました。
しかし2026年4月に初めてJavaに触れ、今後業務でも使う予定であることから、自己研鑽の意味も込めてJavaで競技プログラミングに復帰しました。
その過程で学んだことを備忘録として書き記しておきます。
概要
ダイクストラ法は、重み付きグラフにおける単一始点最短路問題を解くための代表的なアルゴリズムです。
頂点数を $V$、辺数を $E$ とすると、辺の重みが非負である場合に、1つの始点から各頂点への最短距離を $O((V+E)\log V)$ で求められます。
ポイントは、すべての辺の重みが非負であることです。
辺の重みがすべて等しい場合は、1つの始点から各頂点への最短距離を幅優先探索（BFS）で求められます。
BFSでは、次に見る頂点を Queue で管理します。
一方、ダイクストラ法では PriorityQueue を用いて、暫定距離が最も小さい頂点から順に取り出して確定していきます。
この「最も小さい暫定距離を持つ頂点を確定してよい」という性質が成り立つために、すべての辺の重みが非負でなければなりません。
実装
頂点を表すクラス
各頂点はフィールドとして頂点番号と始点からの暫定距離を持つようにします。
また、暫定距離の昇順で比較できるようComparableインターフェースのcompareToメソッドをオーバーライドしておきます。
class Vertex implements Comparable<Vertex> {
int id;
long distFromStart;
public Vertex(int id, long distFromStart) {
this.id = id;
this.distFromStart = distFromStart;
}
@Override
public int compareTo(Vertex v) {
return Long.compare(this.distFromStart, v.distFromStart);
}
}
辺を表すクラス
各々の辺は次のWeightedEdgeクラスとし、すべての辺は隣接リストで管理します。
そのため、各辺が持つフィールドは行先の頂点番号と重みの2つです。
class WeightedEdge {
int to; // 行き先の頂点番号
long weight; // 辺の重み
public WeightedEdge(int vertexId, long weight) {
this.to = vertexId;
this.weight = weight;
}
}
実際のコード
以下がダイクストラ法のコードです。
戻り値は、頂点$i$に対する最短距離minDist[i]が格納された配列minDistです。
ただし、始点からたどり着けない頂点の最短距離はLong.MAX_VALUEになっています。
class Dijkstra {
public static long[] calculateMinDist(int vertexCount, ArrayList<ArrayList<WeightedEdge>> edges, int start) {
long[] minDist = new long[vertexCount]; // 各頂点までの最短距離
boolean[] fixed = new boolean[vertexCount]; // その頂点の最短距離が確定しているかどうか
// 最短距離を十分大きな値にし、未確定に
Arrays.fill(minDist, Long.MAX_VALUE);
Arrays.fill(fixed, false);
// PriorityQueueを用意し、頂点startを挿入。またstartの最短距離を0にする
PriorityQueue<Vertex> q = new PriorityQueue<>();
q.add(new Vertex(start, 0));
minDist[start] = 0;
while (!q.isEmpty()) {
// qの先頭の頂点を取ってくる
Vertex current = q.poll();
int currentId = current.id;
if (fixed[currentId]) {
continue;
}
// 取ってきた頂点に隣接する頂点について、最短距離を更新
fixed[currentId] = true;
for (WeightedEdge w : edges.get(currentId)) {
if (minDist[w.to] > minDist[currentId] + w.weight) {
minDist[w.to] = minDist[currentId] + w.weight;
q.add(new Vertex(w.to, minDist[w.to]));
}
}
}
return minDist;
}
}
所感
やっていることの大枠は幅優先探索に近いため、それと比較しながら理解するとわかりやすいです。
今回は始点から各頂点への最短距離のみを求めましたが、実際には「どの頂点をたどってそこに至るか」という経路そのものを復元したい場合もあります。
その場合は、「どの頂点から来たか」を記録する配列prevを用意しておき、最短距離を更新する際
prev[w.to] = currentId;
としておけば、ダイクストラ法の実行後に終点から始点へ逆向きにprevをたどることで経路を復元できます。