コード随想録指路：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);
}
}