Почему мой алгоритм поиска A * расширяется примерно до того же числа узлов, что и у Дейкстры

Question

Я реализовал алгоритм A *, расширив этот алгоритм Дейкстры, найденный на этом сайте: https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-in-java-using-priorityqueue/

У меня есть дорожная сеть, состоящая из 300k + узлов, и когда я сравниваю результаты моего A * иДейкстра, в среднем, они оба расширяют одинаковое количество узлов. Например, Dijkstra's может расширяться на 250 000, а A * - на 248 000. У меня также есть реализация двунаправленной Dijkstra, которая сокращает его до 100 000 узлов, делая его намного более эффективным с этого момента. Из-за дополнительных затрат на вычисление эвристики A * также требуется больше времени для вычисления кратчайшего расстояния по сравнению с Дейкстрой.

Я получаю одинаковое расстояние по всем алгоритмам, поэтому мой эвристический алгоритм должен быть правильным, поскольку он не переоценивает.

    public SearchPair search(List<List<Node>> adj, int src, int dest) {
        this.adj = adj;
        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        pq = new PriorityQueue<Node>(V, new Node());
        settled = new HashSet<Integer>();

        double heuristic = euclidean(src, dest);
        pq.add(new Node(src, heuristic));
        dist[src] = 0;
        while (!pq.isEmpty()) {
            int currentNode = pq.remove().nodeid;
            if (currentNode == dest) {
                break;
            }
            if (settled.contains(currentNode)) {
                continue;
            }
            settled.add(currentNode);
            expNeighbours(currentNode, dest);
        }
        return new SearchPair(dist[dest], settled.size());
    }

    private void expNeighbours(int currentNode, int dest) {
        //Loop through every neighbour of currentNode
        for (int i = 0; i < adj.get(currentNode).size(); i++) {
            Node neighbour = adj.get(currentNode).get(i);

            if (!settled.contains(neighbour.nodeid)) {
                double edgeDist = neighbour.cost;
                double heuristic = euclidean(neighbour.nodeid, dest);
                double newDist = dist[currentNode] + edgeDist;

                if (newDist < dist[neighbour.nodeid]) {
                    dist[neighbour.nodeid] = (int) newDist;
                    neighbour.prevnode = currentNode;
                }

                pq.add(new Node(neighbour.nodeid, newDist + heuristic));
            }
        }
    }

    private double euclidean(int currentNode, int endNode) {
        //Coords is an ArrayList<Coord> of Lat/Lon objects
        double lon1 = coords.get(currentNode).longitude;
        double lat1 = coords.get(currentNode).latitude;
        double lon2 = coords.get(endNode).longitude;
        double lat2 = coords.get(endNode).latitude;
        //System.out.println("Lat + Lon: " + lat1 + " " + lon1);

        double lat = lat1 - lat2;
        double lon = lon1 - lon2;
        lat = lat * lat;
        lon = lon * lon;
        return (Math.sqrt(lat + lon));
    }

Если бы кто-нибудь мог определить, что может вызвать расширение A * таким количеством узлов, это было бы очень полезно. Спасибо!