Code LeetCode Guide: https://programmercarl.com/
Dijkstra Naive Version#
Dijkstra Algorithm: An algorithm for finding the shortest path from a starting point to other nodes in a weighted graph (with non-negative weights).
- Dijkstra's algorithm can simultaneously find the shortest path from the starting point to all nodes.
- Weights cannot be negative.
In Dijkstra's algorithm, a minDist array is used to record the minimum distance from each node to the source point.
Dijkstra's Trilogy
- First step, select the closest node to the source point that has not been visited.
- Second step, mark this closest node as visited.
- Third step, update the distances from unvisited nodes to the source point (i.e., update the minDist array).
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt(); // Number of nodes
int M = input.nextInt(); // Number of edges
// Record the weights of edges in the directed graph
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();
// Record the shortest length of paths from the starting point to all nodes
int[] minDist = new int[N];
for (int i = 0; i < N; i++) {
minDist[i] = Integer.MAX_VALUE;
}
minDist[0] = 0; // Initialize the distance from the starting point to 0
// Record whether a node has been selected (visited)
boolean[] visited = new boolean[N];
// Trilogy executed N times to ensure the shortest distance is calculated
for (int i = 0; i < N; i++) {
int min = Integer.MAX_VALUE;
int cur = 0;
// Select the closest unvisited node to the starting point
for (int j = 0; j < N; j++) {
if (!visited[j] && minDist[j] < min) {
min = minDist[j];
cur = j;
}
}
// Mark this node as visited
visited[cur] = true;
// Update the values in the minDist array
for (int j = 0; j < N; j++) {
if (!visited[j] && 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]);
}
}
}
- Time complexity: O(n^2)
Dijkstra Heap Optimized Version#
The time complexity of the naive version of Dijkstra is O(n^2), which only relates to n (the number of nodes).
If n is very large, we can prioritize performance from the perspective of the number of edges.
The main differences from the naive version of Dijkstra are two points:
- Different representation of the adjacency list
- Use a priority queue (min-heap) to sort the newly linked edges
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(); // Number of nodes
int M = input.nextInt(); // Number of edges
// Adjacency list to record the weights of edges in the directed graph
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();
// Record the shortest length of paths from the starting point to all nodes
int[] minDist = new int[N];
for (int i = 0; i < N; i++) {
minDist[i] = Integer.MAX_VALUE;
}
minDist[0] = 0; // Initialize the distance from the starting point to 0
// Record whether a node has been selected (visited)
boolean[] visited = new boolean[N];
// Initialize the priority queue (min-heap), <node, distance from the starting point>
PriorityQueue<Pair> pq = new PriorityQueue<>(new MyComparison());
pq.add(new Pair(0, 0));
// Traverse edges
while (!pq.isEmpty()) {
// Select the closest unvisited node to the starting point, implemented with a priority queue
Pair cur = pq.poll();
// Mark this node as visited
visited[cur.node] = true;
// Update the values in the minDist array, traverse the edges connected to the current node
for (Edge edge : grid.get(cur.node)) {
if (!visited[edge.to] && 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])); // Similar to breadth-first search or level-order traversal
}
}
}
if (minDist[N - 1] == Integer.MAX_VALUE) {
System.out.println(-1);
} else {
System.out.println(minDist[N - 1]);
}
}
}
Note: If using lambda expressions for sorting, it may time out.
- Time complexity: O(E * (N + logE)), where E is the number of edges and N is the number of nodes.
while (!pq.empty()) has a time complexity of E, while each element retrieval inside the while loop has a time complexity of logE, along with a for loop with a time complexity of N.
In summary, Dijkstra's algorithm is a greedy strategy that selects the closest node to update the shortest distance each time, and its heap-optimized version also has the characteristics of breadth-first search.
Bellman-Ford#
This problem is a classic single-source shortest path problem with negative weights, which can be solved using the Bellman-Ford algorithm.
The core idea of the Bellman-Ford algorithm is to perform relaxation on all edges n-1 times (where n is the number of nodes) to find the target shortest path.
If a shorter path to node B can be obtained through edge A to B, i.e., if minDist[B] > minDist[A] + value, then we update minDist[B] = minDist[A] + value, this process is called "relaxation".
(In fact, the Bellman-Ford algorithm uses the idea of dynamic programming, which breaks a problem into multiple decision stages and calculates the global optimal solution through recursive relationships between states.)
Relaxing all edges once is equivalent to calculating the shortest distance from the starting point to nodes directly connected to the starting point. Relaxing all edges twice can yield the shortest distance to nodes connected by two edges from the starting point...
If the number of nodes is n, then the maximum number of edges connecting the starting point to the endpoint is n-1. Therefore, regardless of the graph's structure or the order of edges, relaxing all edges n-1 times will definitely yield the shortest distance from the starting point to the endpoint, while also calculating the shortest distance from the starting point to all nodes.
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // Number of nodes
int m = input.nextInt(); // Number of edges
// edges stores all 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 stores the minimum weight from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // Starting point
// Perform relaxation on all edges n-1 times
for (int i = 0; i < n - 1; i++) {
// Traverse all edges
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]);
}
}
}
- Time complexity: O(N * E), where N is the number of nodes and E is the number of edges in the graph.
Bellman-Ford Queue Optimization Algorithm (SPFA)#
The Bellman-Ford algorithm performs relaxation on all edges each time, which actually does some unnecessary work. It only needs to relax the edges connected to the nodes updated during the last relaxation.
Use a queue to record the nodes updated during the last relaxation.
To know which nodes are connected by a node as a starting point, an adjacency list is needed to store the graph.
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(); // Number of nodes
int m = input.nextInt(); // Number of edges
// Adjacency list to store all edges
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 stores the minimum weight from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // Starting point
// Use a queue to record the nodes updated during the last relaxation
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
// visited records the elements in the queue
boolean[] visited = new boolean[n];
visited[0] = true;
// Perform relaxation on all edges from all nodes in the queue
while (!queue.isEmpty()) {
int from = queue.poll();
visited[from] = false;
for (Edge edge : grid.get(from)) {
// Start relaxation
if (minDist[from] + edge.weight < minDist[edge.to]) {
minDist[edge.to] = minDist[from] + edge.weight;
if (!visited[edge.to]) {
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]);
}
}
}
Generally speaking, the time complexity of SPFA is O(K * N), where K is an indefinite value, because the number of times a node needs to be added to the queue depends on the density of the graph. In the worst case, it is O(N * E).
Bellman-Ford to Detect Negative Weight Cycles#
A negative weight cycle is a situation where there is a cycle in the graph and the total weight of the edges in the cycle is negative.
If the shortest path is sought in such a graph, it will loop infinitely within this cycle (as negative numbers + negative numbers will only get smaller), making it impossible to find the shortest path. Therefore, when seeking the shortest path in a graph with negative weights, we must first check if there is a negative weight cycle in the graph.
In the Bellman-Ford algorithm, relaxing all edges n-1 times can find the shortest path from the starting point to any node. If we relax the edges more than n times, the results in the minDist array (which records the shortest distances from the starting point to other nodes) will not change.
However, in the case of a negative weight cycle, there will always be a shorter path, so after the nth relaxation, the minDist array will also change.
Thus, we only need to relax once more and check if the minDist array changes.
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // Number of nodes
int m = input.nextInt(); // Number of edges
// edges stores all 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 stores the minimum weight from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // Starting point
// Flag to record if minDist changes during the nth relaxation
boolean flag = false;
// Relax all edges n times
for (int i = 0; i < n; i++) {
// Traverse all edges
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) {
System.out.println("circle");
return;
}
if (minDist[n - 1] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
System.out.println(minDist[n - 1]);
}
}
}
The queue-optimized version of Bellman-Ford (SPFA) can also be used.
In extreme cases, i.e., when every node is connected to every other node and each node has an in-degree of n-1 (where n is the number of nodes), each node can be added to the queue at most n-1 times.
If the number of times a node is added to the queue exceeds n-1, then the graph must contain a negative weight cycle.
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(); // Number of nodes
int m = input.nextInt(); // Number of edges
// Adjacency list to store all edges
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 stores the minimum weight from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // Starting point
// Use a queue to record the nodes updated during the last relaxation
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
// visited records the elements in the queue
boolean[] visited = new boolean[n];
visited[0] = true;
// count records the number of times all nodes have been added to the queue
int[] count = new int[n];
count[0]++;
// Perform relaxation on all edges from all nodes in the queue
while (!queue.isEmpty()) {
int from = queue.poll();
visited[from] = false;
for (Edge edge : grid.get(from)) {
// Start relaxation
if (minDist[from] + edge.weight < minDist[edge.to]) {
minDist[edge.to] = minDist[from] + edge.weight;
if (!visited[edge.to]) {
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 Single Source Limited Shortest Path#
Reviewing the Bellman-Ford algorithm:
- Relaxing all edges once is equivalent to calculating the shortest distance from the starting point to nodes directly connected to the starting point.
- With n nodes, the maximum number of edges connecting the starting point to the endpoint is n-1. Therefore, relaxing all edges n-1 times will definitely yield the shortest distance from the starting point to the endpoint.
If at most k cities can be passed through, then it means k + 1 edges are connected to the nodes. This means we need to find the shortest distance from the starting point to the endpoint while passing through at most k + 1 edges. We can relax all edges k + 1 times.
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // Number of nodes
int m = input.nextInt(); // Number of edges
// edges stores all 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 stores the minimum weight from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0; // Starting point
// Record the values of minDist after the last relaxation
int[] minDist_copy = new int[n];
// Relax all edges k + 1 times
for (int i = 0; i < k + 1; i++) {
for (int j = 0; j < n; j++) {
minDist_copy[j] = minDist[j];
}
// Traverse all edges
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]);
}
}
}
- Time complexity: O(K * E), where K is the maximum number of nodes that can be passed through and E is the number of edges in the graph.
Due to the influence of negative weight cycles, the order of edges, etc., it may cause the calculation of the minDist array to be based on the current relaxation's minDist values rather than the previous relaxation's minDist values.
Therefore, when calculating minDist each time, it must be based on the minDist values from the last relaxation of all edges.
- This problem can have negative weight cycles, indicating that as long as more relaxations are performed, the results will change.
- This problem requires passing through at most k nodes, which limits the number of relaxations.
In SPFA, to control the relaxation for k times, a variable que_size can be used to record the number of nodes added to the queue in each round of relaxation. In the next round of relaxation, the que_size nodes in the queue can be popped out, which are the nodes added to the queue in the previous round of relaxation.
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(); // Number of nodes
int m = input.nextInt(); // Number of edges
// Adjacency list to store all edges
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 stores the minimum weight from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0; // Starting point
// Use a queue to record the nodes updated during the last relaxation
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(src);
// minDist_copy records the values after the last relaxation
int[] minDist_copy = new int[n];
int queue_size;
k++;
// Perform k + 1 relaxations on all edges from all nodes in the queue
while ((k-- > 0) && !queue.isEmpty()) {
for (int i = 0; i < n; i++) {
minDist_copy[i] = minDist[i];
}
queue_size = queue.size();
// visited controls that no duplicate elements are added to the queue in each round of relaxation
boolean[] visited = new boolean[n];
while ((queue_size--) > 0) {
int from = queue.poll();
visited[from] = false;
for (Edge edge : grid.get(from)) {
// Start relaxation
if (minDist_copy[from] + edge.weight < minDist[edge.to]) {
minDist[edge.to] = minDist_copy[from] + edge.weight;
if (!visited[edge.to]) {
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#
Multi-source shortest path, i.e., finding multiple shortest paths from multiple starting points to multiple endpoints.
The core idea of the Floyd algorithm is dynamic programming.
Three layers of for loops, the key is to understand the traversal order.
import java.util.*;;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt(); // Number of nodes, node numbers from 1 to N
int M = input.nextInt(); // Number of roads
int[][] grid = new int[N + 1][N + 1]; // Adjacency matrix
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; // Bidirectional road
}
int Q = input.nextInt(); // Number of sightseeing plans
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 to find multi-source shortest paths
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]);
}
}
}
}
- Time complexity: O(n^3)
The Floyd algorithm has a relatively high time complexity and is suitable for dense graphs with many sources.
If there are few sources, multiple Dijkstra algorithms can be used to find the shortest paths from the sources to the endpoints.
A* (A star)#
In chess, the knight and the elephant move according to the rules "knight moves in an L shape" and "elephant moves diagonally". Given the starting coordinates and target coordinates of the knight, calculate the shortest number of steps required to reach the target point according to the knight's movement rules.
Breadth-first search:
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(); // Number of test cases
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]) {
board[x][y] = true;
queue.add(new Position(x, y));
}
}
}
count++;
}
}
}
In breadth-first search, many unnecessary traversals are made. If we can direct the traversal towards the target, we can avoid many unnecessary traversals.
A* is an improved version of breadth-first search or Dijkstra's algorithm, with the key being the heuristic function, which influences the order in which elements are taken from the container (queue).
BFS is non-directional, searching layer by layer, while A is directional, searching towards the target*, which can save many unnecessary traversal steps.
The heuristic function should influence the sorting of elements in the queue. To sort the nodes in the queue, we need to assign a weight to each node, where the weight of each node is F, given by the formula: F = G + H, where G is the distance from the starting point to the currently traversed node, and F is the distance from the currently traversed node to the endpoint.
The distance from the starting point to the currently traversed node plus the distance from the currently traversed node to the endpoint gives the total distance from the starting point to the endpoint.
In an unweighted grid, there are usually three ways to calculate the distance between two points:
- Manhattan distance: d = abs(x1-x2) + abs(y1-y2)
- Euclidean distance: d = sqrt((x1-x2)^2 + (y1-y2)^2)
- Chebyshev distance: d = max(abs(x1 - x2), abs(y1 - y2))
In this problem, using Euclidean distance can best reflect the distance between points.
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; // Knight moves in an L shape, 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);
}
}