Class AStar

src/main/java/com/thealgorithms/datastructures/graphs/AStar.java:14–144

AStar class implements the A pathfinding algorithm to find the shortest path in a graph. The graph is represented using an adjacency list, and the algorithm uses a heuristic to estimate the cost to reach the destination node. Time Complexity = O(E), where E is equal to the number of edges

 * Time Complexity = O(E), where E is equal to the number of edges
 */
public final class AStar {
    private AStar() {
    }

    /**
     * Represents a graph using an adjacency list.
     */
    static class Graph {
        private ArrayList<ArrayList<Edge>> graph;

        Graph(int size) {
            this.graph = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                this.graph.add(new ArrayList<>());
            }
        }

        private ArrayList<Edge> getNeighbours(int from) {
            return this.graph.get(from);
        }

        // Add a bidirectional edge to the graph
        private void addEdge(Edge edge) {
            this.graph.get(edge.getFrom()).add(new Edge(edge.getFrom(), edge.getTo(), edge.getWeight()));
            this.graph.get(edge.getTo()).add(new Edge(edge.getTo(), edge.getFrom(), edge.getWeight()));
        }
    }

    /**
     * Represents an edge in the graph with a start node, end node, and weight.
     */
    private static class Edge {
        private int from;
        private int to;
        private int weight;

        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public int getFrom() {
            return from;
        }

        public int getTo() {
            return to;
        }

        public int getWeight() {
            return weight;
        }
    }

    /**
     * Contains information about the path and its total distance.
     */