コード随想録指路：https://programmercarl.com/
dijkstra 朴素版#
dijkstra アルゴリズム：重み付きグラフ（重みが非負の数）において、始点から他のノードへの最短経路を求めるアルゴリズム。
- dijkstra アルゴリズムは、始点からすべてのノードへの最短経路を同時に求めることができる
- 重みは負の数であってはいけない
dijkstra アルゴリズムでは、minDist 配列を使用して、各ノードの始点からの最小距離を記録する。
dijkstra 三部曲
- 第一歩、始点からどのノードが近く、そのノードが未訪問であることを選ぶ
- 第二歩、その最近接ノードを訪問済みとしてマークする
- 第三歩、未訪問ノードの始点までの距離を更新する（つまり、minDist 配列を更新する）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt(); // ノード数
int M = input.nextInt(); // 辺数
// 有向グラフの辺の重みを記録する
int[][] grid = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < M; i++) {
int S = input.nextInt();
int E = input.nextInt();
int V = input.nextInt();
grid[S - 1][E - 1] = V;
}
input.close();
// 始点からすべてのノードへの経路の最短長を記録する
int[] minDist = new int[N];
for (int i = 0; i < N; i++) {
minDist[i] = Integer.MAX_VALUE;
}
minDist[0] = 0; // 始点の距離を初期化する
// ノードが選択（訪問）されたかどうかを記録する
boolean[] visited = new boolean[N];
// 三部曲をN回実行し、最短距離を計算する
for (int i = 0; i < N; i++) {
int min = Integer.MAX_VALUE;
int cur = 0;
// 始点から最も近く、未訪問のノードを選択する
for (int j = 0; j < N; j++) {
if (visited[j] == false && minDist[j] < min) {
min = minDist[j];
cur = j;
}
}
// このノードを訪問済みとしてマークする
visited[cur] = true;
// minDist配列の値を更新する
for (int j = 0; j < N; j++) {
if (visited[j] == false && grid[cur][j] != Integer.MAX_VALUE && minDist[j] > grid[cur][j] + min) {
minDist[j] = grid[cur][j] + min;
}
}
}
if (minDist[N - 1] == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minDist[N - 1]);
}
}
}
- 時間計算量：O (n^2)
dijkstra 堆优化版#
朴素版の dijkstra の時間計算量は O (n^2) で、n（ノードの数）に依存します。
もし n が非常に大きい場合、エッジの数から性能を優先する別の視点に切り替えることができます。
朴素版 dijkstra との主な違いは 2 点です：
- 隣接リストの表現方法が異なる
- 優先度キュー（小さいヒープ）を使用して新しいリンクのエッジをソートする
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
class Pair {
int node, dist;
Pair(int node, int dist) {
this.node = node;
this.dist = dist;
}
}
class MyComparison implements Comparator<Pair> {
@Override
public int compare(Pair lhs, Pair rhs) {
return Integer.compare(lhs.dist, rhs.dist);
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt(); // ノード数
int M = input.nextInt(); // 辺数
// 隣接リストで有向グラフの辺の重みを記録する
List<List<Edge>> grid = new ArrayList<>();
for (int i = 0; i < N; i++) {
grid.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
int S = input.nextInt();
int E = input.nextInt();
int V = input.nextInt();
grid.get(S - 1).add(new Edge(E - 1, V));
}
input.close();
// 始点からすべてのノードへの経路の最短長を記録する
int[] minDist = new int[N];
for (int i = 0; i < N; i++) {
minDist[i] = Integer.MAX_VALUE;
}
minDist[0] = 0; // 始点の距離を初期化する
// ノードが選択（訪問）されたかどうかを記録する
boolean[] visited = new boolean[N];
// 優先度キュー（小さいヒープ）を初期化する、<ノード、始点からそのノードまでの距離>
PriorityQueue<Pair> pq = new PriorityQueue<>(new MyComparison());
pq.add(new Pair(0, 0));
// エッジを遍歴する
while (!pq.isEmpty()) {
// 始点から最も近く、未訪問のノードを選択する、優先度キューを実装する
Pair cur = pq.poll();
// このノードを訪問済みとしてマークする
visited[cur.node] = true;
// minDist配列の値を更新する、curが指すノードとエッジを遍歴する
for (Edge edge : grid.get(cur.node)) {
if (visited[edge.to] == false && minDist[edge.to] > minDist[cur.node] + edge.weight) {
minDist[edge.to] = minDist[cur.node] + edge.weight;
pq.add(new Pair(edge.to, minDist[edge.to])); // 幅優先探索や層順遍歴に似ている
}
}
}
if (minDist[N - 1] == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minDist[N - 1]);
}
}
}
注意、ラムダ式を使用してソートを行うと、タイムアウトが発生します。
- 時間計算量：O (E * (N + logE)) E はエッジの数、N はノードの数
while (!pq.empty())の時間計算量は E で、while の中で要素を取得する時間計算量は logE で、for ループの時間計算量は N です。
全体として、dijkstra アルゴリズムは貪欲な戦略であり、毎回最も近いノードを選択して最短距離を更新します。そのヒープ最適化バージョンは、幅優先探索の影響を受けています。
Bellman_ford#
本題は、負の重みを持つ単一始点最短経路問題の古典的な例です。Bellman_ford アルゴリズムを使用してこの種の問題を解決できます。
Bellman_ford アルゴリズムの核心思想は、すべてのエッジに対して n-1 回の緩和操作を行い（n はノードの数）、目的の最短経路を求めることです。
もし A から B へのエッジを通じて B ノードへの到達経路が短くなる場合、つまりminDist[B] > minDist[A] + valueであれば、minDist[B] = minDist[A] + valueを更新します。このプロセスを「緩和」と呼びます。
（実際、Bellman_ford アルゴリズムは動的計画法の考え方を採用しています。すなわち、問題を複数の意思決定段階に分解し、状態間の再帰関係を通じて最終的にグローバルな最適解を計算します。）
すべてのエッジを 1 回緩和することは、始点から始点に 1 つのエッジで接続されたノードへの最短距離を計算することに相当します。すべてのエッジを 2 回緩和すると、始点に 2 つのエッジで接続されたノードへの最短距離が得られます......
ノード数が n の場合、始点から終点まで、最大で n-1 本のエッジが接続されます。したがって、グラフがどのようなものであっても、エッジの順序がどうであっても、すべてのエッジを n-1 回緩和すれば、始点から終点への最短距離を必ず得ることができます。同時に、始点からすべてのノードへの最短距離も計算されます。
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // ノード数
int m = input.nextInt(); // 辺数
// edgesにすべてのエッジを格納する
int[][] edges = new int[m][3];
for (int i = 0; i < m; i++) {
int s = input.nextInt() - 1;
int t = input.nextInt() - 1;
int v = input.nextInt();
edges[i] = new int[] { s, t, v };
}
input.close();
// minDistにすべてのノードから始点までの最小重みを格納する
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // 始点
// すべてのエッジに対してn-1回緩和を行う
for (int i = 0; i < n - 1; i++) {
// すべてのエッジを遍歴する
for (int j = 0; j < m; j++) {
int from = edges[j][0];
int to = edges[j][1];
int value = edges[j][2];
if (minDist[from] == Integer.MAX_VALUE) {
continue;
}
minDist[to] = Math.min(minDist[to], minDist[from] + value);
}
}
if (minDist[n - 1] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(minDist[n - 1]);
}
}
}
- 時間計算量：O (N * E) , N はノードの数、E はグラフ中のエッジの数
Bellman_ford 队列优化算法 (SPFA)#
Bellman_ford アルゴリズムは、毎回すべてのエッジに対して緩和を行うため、実際には無駄な作業が多くなります。前回の緩和で更新されたノードを出発点として接続されたエッジだけを緩和すれば十分です。
前回の緩和で更新されたノードを記録するためにキューを使用します。
あるノードが出発点としてどのノードに接続されているかを知るためには、隣接リストを使用してこのグラフを保存する必要があります。
import java.util.*;;
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // ノード数
int m = input.nextInt(); // 辺数
// 隣接リストにすべてのエッジを格納する
List<List<Edge>> grid = new ArrayList<>();
for (int i = 0; i < n; i++) {
grid.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int s = input.nextInt() - 1;
int t = input.nextInt() - 1;
int v = input.nextInt();
grid.get(s).add(new Edge(t, v));
}
input.close();
// minDistにすべてのノードから始点までの最小重みを格納する
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // 始点
// 前回更新されたノードを記録するためのキュー
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
// visitedはキュー内の要素を記録する
boolean[] visited = new boolean[n];
visited[0] = true;
// キュー内のすべてのノードから出発するすべてのエッジに対して緩和を行う
while (!queue.isEmpty()) {
int from = queue.poll();
visited[from] = false;
for (Edge edge : grid.get(from)) {
// 緩和を開始する
if (minDist[from] + edge.weight < minDist[edge.to]) {
minDist[edge.to] = minDist[from] + edge.weight;
if (visited[edge.to] == false) {
queue.offer(edge.to);
visited[edge.to] = true;
}
}
}
}
if (minDist[n - 1] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(minDist[n - 1]);
}
}
}
一般的に、SPFA の時間計算量は O (K * N) K は不定値です。ノードがキューに入る回数はグラフの密度によって異なります。最悪の場合は O (N * E) です。
Bellman_ford 之判断负权回路#
負の重みのサイクル、つまり、グラフ内にサイクルが存在し、そのサイクル上のエッジの総重みが負である状況です。
このようなグラフで最短経路を求めると、そのサイクル内で無限にループしてしまいます（負の数 + 負の数はどんどん小さくなるだけで）、最短経路を求めることができません。したがって、負の重みを持つグラフで最短経路を求める場合は、まずそのグラフに負の重みのサイクルがないかを確認する必要があります。
bellman_ford アルゴリズムでは、すべてのエッジを n-1 回緩和することで、始点から任意のノードへの最短経路を求めることができます。n 回以上緩和すると、minDist 配列（他のノードへの最短距離を記録する）は変化しません。
負の重みのサイクルがある場合、常により短い最短経路が存在するため、n 回目の緩和で minDist 配列も変化します。
したがって、もう 1 回緩和を行い、minDist 配列が変化するかどうかを確認するだけです。
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // ノード数
int m = input.nextInt(); // 辺数
// edgesにすべてのエッジを格納する
int[][] edges = new int[m][3];
for (int i = 0; i < m; i++) {
int s = input.nextInt() - 1;
int t = input.nextInt() - 1;
int v = input.nextInt();
edges[i] = new int[] { s, t, v };
}
input.close();
// minDistにすべてのノードから始点までの最小重みを格納する
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // 始点
// n回の緩和でminDistが変化するかどうかを記録するためのフラグ
boolean flag = false;
// すべてのエッジに対してn回緩和を行う
for (int i = 0; i < n; i++) {
// すべてのエッジを遍歴する
for (int j = 0; j < m; j++) {
int from = edges[j][0];
int to = edges[j][1];
int value = edges[j][2];
if (minDist[from] == Integer.MAX_VALUE) {
continue;
}
if (minDist[to] > minDist[from] + value) {
if (i < n - 1) {
minDist[to] = minDist[from] + value;
} else {
flag = true;
}
}
}
}
if (flag == true) {
System.out.println("circle");
return;
}
if (minDist[n - 1] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(minDist[n - 1]);
}
}
}
SPFA の最適化版を使用することもできます。
極端な場合、すべてのノードが他のノードに接続されており、各ノードの入次数が n-1（n はノードの数）である場合、各ノードは最大で n-1 回キューに入ることになります。
ノードがキューに入る回数が n-1 回を超える場合、そのグラフには必ず負の重みのサイクルがあります。
import java.util.*;;
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // ノード数
int m = input.nextInt(); // 辺数
// 隣接リストにすべてのエッジを格納する
List<List<Edge>> grid = new ArrayList<>();
for (int i = 0; i < n; i++) {
grid.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int s = input.nextInt() - 1;
int t = input.nextInt() - 1;
int v = input.nextInt();
grid.get(s).add(new Edge(t, v));
}
input.close();
// minDistにすべてのノードから始点までの最小重みを格納する
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // 始点
// 前回更新されたノードを記録するためのキュー
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
// visitedはキュー内の要素を記録する
boolean[] visited = new boolean[n];
visited[0] = true;
// countはすべてのノードの入隊回数を記録する
int[] count = new int[n];
count[0]++;
// キュー内のすべてのノードから出発するすべてのエッジに対して緩和を行う
while (!queue.isEmpty()) {
int from = queue.poll();
visited[from] = false;
for (Edge edge : grid.get(from)) {
// 緩和を開始する
if (minDist[from] + edge.weight < minDist[edge.to]) {
minDist[edge.to] = minDist[from] + edge.weight;
if (visited[edge.to] == false) {
queue.offer(edge.to);
visited[edge.to] = true;
if (count[edge.to]++ == n) {
System.out.println("circle");
return;
}
}
}
}
}
if (minDist[n - 1] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(minDist[n - 1]);
}
}
}
Bellman_ford 之单源有限最短路#
Bellman_ford アルゴリズムを振り返ると：
- すべてのエッジを 1 回緩和することは、始点から始点に 1 つのエッジで接続されたノードへの最短距離を計算することに相当します。
- ノード数が n の場合、始点から終点まで、最大で n-1 本のエッジが接続されます。したがって、すべてのエッジを n-1 回緩和すれば、始点から終点への最短距離を必ず得ることができます。
もし最大で k 個の都市を通過する場合、k + 1 本のエッジで接続されたノードを求めます。つまり、始点から最大で k + 1 本のエッジで終点に到達する最短距離を求めることになります。すべてのエッジを k + 1 回緩和すればよいのです。
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // ノード数
int m = input.nextInt(); // 辺数
// edgesにすべてのエッジを格納する
int[][] edges = new int[m][3];
for (int i = 0; i < m; i++) {
int s = input.nextInt() - 1;
int t = input.nextInt() - 1;
int v = input.nextInt();
edges[i] = new int[] { s, t, v };
}
int src = input.nextInt() - 1;
int dst = input.nextInt() - 1;
int k = input.nextInt();
input.close();
// minDistにすべてのノードから始点までの最小重みを格納する
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0; // 始点
// 前回の緩和後のminDistの値を記録するための配列
int[] minDist_copy = new int[n];
// すべてのエッジをk + 1回緩和する
for (int i = 0; i < k + 1; i++) {
for (int j = 0; j < n; j++) {
minDist_copy[j] = minDist[j];
}
// すべてのエッジを遍歴する
for (int j = 0; j < m; j++) {
int from = edges[j][0];
int to = edges[j][1];
int value = edges[j][2];
if (minDist_copy[from] == Integer.MAX_VALUE) {
continue;
}
minDist[to] = Math.min(minDist[to], minDist_copy[from] + value);
}
}
if (minDist[dst] == Integer.MAX_VALUE) {
System.out.println("unreachable");
} else {
System.out.println(minDist[dst]);
}
}
}
- 時間計算量：O (K * E) , K は最大で通過するノード数、E はグラフ中のエッジの数
負の重みのサイクル、エッジの順序などの影響により、minDist 配列を計算する際に、今回の緩和の minDist の値に基づいてしまうことがあります。前回の緩和の minDist の値に基づいて計算する必要があります。
- 本題では負の重みのサイクルが存在する可能性があるため、緩和を多く行うことで結果が変わることがあります。
- 本題では最大で k 個のノードを通過することが求められているため、緩和回数に制限があります。
SPFA では、k 回の緩和を制御するために、各ラウンドの緩和でキューに入ったすべてのノードの数を記録する変数 que_size を使用します。次のラウンドの緩和では、キュー内の que_size 個のノードをすべて取り出します。これは前回の緩和でキューに入ったノードです。
import java.util.*;;
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // ノード数
int m = input.nextInt(); // 辺数
// 隣接リストにすべてのエッジを格納する
List<List<Edge>> grid = new ArrayList<>();
for (int i = 0; i < n; i++) {
grid.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int s = input.nextInt() - 1;
int t = input.nextInt() - 1;
int v = input.nextInt();
grid.get(s).add(new Edge(t, v));
}
int src = input.nextInt() - 1;
int dst = input.nextInt() - 1;
int k = input.nextInt();
input.close();
// minDistにすべてのノードから始点までの最小重みを格納する
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0; // 始点
// 前回更新されたノードを記録するためのキュー
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(src);
// minDist_copyは前回の緩和後の値を記録する
int[] minDist_copy = new int[n];
int queue_size;
k++;
// キュー内のすべてのノードから出発するすべてのエッジに対してk + 1回の緩和を行う
while ((k-- > 0) && !queue.isEmpty()) {
for (int i = 0; i < n; i++) {
minDist_copy[i] = minDist[i];
}
queue_size = queue.size();
// visitedは各ラウンドの緩和中にキューに重複する要素が追加されないように制御する
boolean[] visited = new boolean[n];
while ((queue_size--) > 0) {
int from = queue.poll();
visited[from] = false;
for (Edge edge : grid.get(from)) {
// 緩和を開始する
if (minDist_copy[from] + edge.weight < minDist[edge.to]) {
minDist[edge.to] = minDist_copy[from] + edge.weight;
if (visited[edge.to] == false) {
queue.offer(edge.to);
visited[edge.to] = true;
}
}
}
}
}
if (minDist[dst] == Integer.MAX_VALUE) {
System.out.println("unreachable");
} else {
System.out.println(minDist[dst]);
}
}
}
Floyd#
多源最短経路、つまり、複数の始点から複数の終点への多くの最短経路を求めることです。
Floyd アルゴリズムの核心思想は動的計画法です。
3 層の for ループで、重要なのは遍歴順序を理解することです。
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt(); // ノードの数、ノード番号は1からNまで
int M = input.nextInt(); // 道路の数
int[][] grid = new int[N + 1][N + 1]; // 隣接行列
for (int i = 0; i <= N; i++) {
Arrays.fill(grid[i], Integer.MAX_VALUE);
}
for (int i = 0; i < M; i++) {
int u = input.nextInt();
int v = input.nextInt();
int w = input.nextInt();
grid[u][v] = w;
grid[v][u] = w; // 双方向道路
}
int Q = input.nextInt(); // 観光計画の数
int[][] plans = new int[Q][2];
for (int i = 0; i < Q; i++) {
int start = input.nextInt();
int end = input.nextInt();
plans[i][0] = start;
plans[i][1] = end;
}
input.close();
// Floydで多源最短経路を求める
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (grid[i][k] == Integer.MAX_VALUE || grid[k][j] == Integer.MAX_VALUE) {
continue;
}
grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);
}
}
}
for (int i = 0; i < Q; i++) {
int start = plans[i][0];
int end = plans[i][1];
if (grid[start][end] == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(grid[start][end]);
}
}
}
}
- 時間計算量：O (n^3)
floyd アルゴリズムの時間計算量は比較的高く、密なグラフで始点が多い場合に適しています。
始点が少ない場合、実際には複数回 dijkstra を使用して始点から終点を求めることができます。
A * (A star)#
チェスにおいて、馬と象の移動ルールはそれぞれ「馬は日を歩き、象は田を歩く」となっています。現在、騎士の初期座標と目標座標が与えられ、騎士の移動ルールに基づいて、起点から目標点に到達するのに必要な最短ステップ数を計算することが求められています。
幅優先探索：
import java.util.*;;
class Position {
int x, y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int[][] dir = {
{ -2, 1 }, { -2, -1 }, { -1, 2 }, { -1, -2 }, { 1, 2 }, { 1, -2 }, { 2, 1 }, { 2, -1 }
};
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // テストケースの数
for (int i = 0; i < n; i++) {
int a1 = input.nextInt();
int a2 = input.nextInt();
int b1 = input.nextInt();
int b2 = input.nextInt();
bfs(a1, a2, b1, b2);
}
input.close();
}
public static void bfs(int a1, int a2, int b1, int b2) {
boolean[][] board = new boolean[1001][1001];
int count = 0;
Queue<Position> queue = new ArrayDeque<>();
queue.offer(new Position(a1, a2));
board[a1][a2] = true;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Position pos = queue.poll();
if (pos.x == b1 && pos.y == b2) {
System.out.println(count);
return;
}
for (int j = 0; j < 8; j++) {
int x = pos.x + dir[j][0];
int y = pos.y + dir[j][1];
if (x > 0 && x < 1001 && y > 0 && y < 1001 && board[x][y] == false) {
board[x][y] = true;
queue.add(new Position(x, y));
}
}
}
count++;
}
}
}
幅優先探索では、多くの無駄な遍歴が行われます。もし遍歴の方向を終点に向かって進めることができれば、多くの無駄な遍歴を避けることができます。
A * は幅優先探索または dijkstra の改良版であり、重要なのはヒューリスティック関数です。これは、幅優先探索または dijkstra がコンテナ（キュー）から要素を取得する優先順序に影響を与えます。
BFS は目的がなく、円を描いて探索しますが、A * は方向性を持って探索します。これにより、不要な遍歴ステップを大幅に節約できます。
ヒューリスティック関数が影響を与えるのは、キュー内の要素のソートです。キュー内のノードに対して重みを付ける必要があり、各ノードの重みは F であり、次の式が与えられます：F = G + H、G：始点から現在の遍歴ノードまでの距離、F：現在の遍歴ノードから終点までの距離です。
始点から現在の遍歴ノードまでの距離 + 現在の遍歴ノードから終点までの距離が、始点から終点までの距離となります。
無重みのグリッド状では、通常、2 点間の距離を計算する方法は次の 3 つです：
- マンハッタン距離、計算方法：d = abs (x1-x2)+abs (y1-y2)
- ユークリッド距離（オイラー距離）、計算方法：d = sqrt ((x1-x2)^2 + (y1-y2)^2)
- チェビシェフ距離、計算方法：d = max (abs (x1 - x2), abs (y1 - y2))
本題では、ユークリッド距離を採用することで、点と点の間の距離を最大限に表現できます。
import java.util.*;
class Main {
int[][] dir = {
{ -2, 1 }, { -2, -1 }, { -1, 2 }, { -1, -2 }, { 1, 2 }, { 1, -2 }, { 2, 1 }, { 2, -1 }
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Main main = new Main();
for (int i = 0; i < n; i++) {
int[][] moves = new int[1001][1001];
int a1 = sc.nextInt();
int a2 = sc.nextInt();
int b1 = sc.nextInt();
int b2 = sc.nextInt();
main.aStar(a1, a2, b1, b2, moves);
System.out.println(moves[b1][b2]);
}
}
public void aStar(int startx, int starty, int endx, int endy, int[][] moves) {
PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return Integer.compare(a[3], b[3]);
}
});
que.offer(new int[] { startx, starty, 0,
compute(startx, starty, endx, endy) });
while (!que.isEmpty()) {
int[] cur = que.poll();
int curx = cur[0];
int cury = cur[1];
// System.out.println(curx + " " + cury);
if (curx == endx && cury == endy) {
break;
}
for (int i = 0; i < 8; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 1 || nextx > 1000 || nexty < 1 || nexty > 1000) {
continue;
}
if (moves[nextx][nexty] != 0) {
continue;
}
moves[nextx][nexty] = moves[curx][cury] + 1;
int g = cur[2] + 5; // 馬が日を歩く、1 * 1 + 2 * 2 = 5
int h = compute(nextx, nexty, endx, endy);
que.offer(new int[] { nextx, nexty, g, g + h });
}
}
}
public int compute(int x1, int y1, int x2, int y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
}