Code LeetCode Guide: https://programmercarl.com/
Dijkstra Naive Version#
Dijkstra's algorithm: An algorithm for finding the shortest path from a starting point to other nodes in a weighted graph (with non-negative weights).
- The Dijkstra 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.
Dijkstra's Trilogy
- First, select the node closest to the source that has not been visited.
- Second, mark this closest node as visited.
- Third, update the distances from the non-visited nodes to the source (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 the path 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 repeated 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 node to the starting point that has not been visited
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 change our perspective to prioritize performance based on 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 the path 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 node to the starting point that has not been visited, implemented by the 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 from the node pointed to by cur
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 cause timeout.
- 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 having a time complexity of N.
Overall, 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 shadow 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 relax 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 adopts the idea of dynamic programming, which decomposes 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 connected by one edge from the starting point. Relaxing all edges twice can yield the shortest distance to nodes connected by two edges from the starting point...
With n nodes, the maximum number of edges connecting the starting point to the endpoint is n-1. Therefore, regardless of the structure of the graph or the order of the 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 weights from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // Starting point
// Relax 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 relaxes 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 weights 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;
// Relax 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 relaxing
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, 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, it is necessary to 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 all 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 weights from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0; // Starting point
// Used to record whether 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, if all nodes are connected to every other node, each node can be added to the queue up to n-1 times (where n is the number of nodes).
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 weights 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]++;
// Relax 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 relaxing
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 connected by one edge from the starting point.
- With n nodes, the maximum number of edges connecting the starting point to the endpoint is n-1. Thus, relaxing all edges n-1 times will definitely yield the shortest distance from the starting point to the endpoint.
If at most k cities are to be passed through, then 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 weights from all nodes to the starting point
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[src] = 0; // Starting point
// Used to 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 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., the calculation of the minDist array may 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 at most k nodes to be passed through, 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, all nodes in the queue for que_size will 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 weights 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++;
// Relax all edges from all nodes in the queue for k + 1 times
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 relaxing
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 runs can be used to find the shortest path from the source to the endpoint.
A* (A star)#
In chess, the knight's and bishop's movement rules are "knight moves in an L shape" and "bishop moves diagonally". Given the starting and target coordinates of the knight, calculate the shortest number of moves required to reach the target point based on 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 the traversal direction can be oriented towards the target, many unnecessary traversals can be avoided.
A* is an improved version of breadth-first search or Dijkstra, with the key being the heuristic function, which influences the priority order of elements 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 is meant to influence the sorting of elements in the queue. To sort the nodes in the queue, each node needs a weight, and 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, calculated as: d = abs(x1-x2)+abs(y1-y2)
- Euclidean distance, calculated as: d = sqrt((x1-x2)^2 + (y1-y2)^2)
- Chebyshev distance, calculated as: 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 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);
}
}