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).
- The Dijkstra algorithm can simultaneously find the shortest path from the starting point to all nodes.
- Weights cannot be negative.
In the Dijkstra algorithm, a minDist array is used to record the minimum distance from each node to the source point.
Dijkstra Trilogy
- First, select the node closest to the source point that has not been visited.
- Second, mark this closest node as visited.
- Third, 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 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 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 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 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 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 nodes and edges 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 with a time complexity of N.
In summary, the Dijkstra algorithm is a greedy strategy that selects the closest node each time to update the shortest distance, and its heap-optimized version has a 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 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
// 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 is sufficient to relax only 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;
// 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 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]);
}
}
}
In general, the time complexity of SPFA is O(K * N), where K is an indefinite value, as 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 + negative 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, and relaxing more than n times will not change the results in the minDist array (which records the shortest distances from the starting point to other nodes).
In the case of a negative weight cycle, there will always be a shorter shortest 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
// Used to record whether the 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, with each node having an in-degree of n-1 (where n is the number of nodes), then 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]++;
// 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 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 for 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. 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 are to be passed through, then there are k + 1 edges connecting 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. Relaxing all edges k + 1 times will suffice.
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
// 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 to 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., the calculation of the minDist array may be based on the current relaxation's minDist values rather than the values from the last relaxation.
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 result will change.
- This problem requires passing through at most k nodes, which limits the number of relaxations.
In SPFA, to control the number of relaxations to 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 from the previous round's que_size can be popped out.
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++;
// 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 the addition of duplicate elements 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 nested 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 path from the source to the endpoint.
A* (A star)#
In chess, the movement rules of the knight and the bishop are "knight moves in an L shape" and "bishop moves diagonally". Given the starting coordinates and target coordinates of the knight, calculate the shortest number of moves 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 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 aimless, searching layer by layer, while A searches in a directed manner*, 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, each node is assigned a weight, with the weight of each node being F, given by the formula: F = G + H, where G is the distance from the starting point to the currently traversed node, and H is the distance from the currently traversed node to the target.
The distance from the starting point to the currently traversed node plus the distance from the currently traversed node to the target gives the total distance from the starting point to the target.
In an unweighted grid, there are usually three common methods 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);
}
}