算法优化，最短路径。

Question

1. 问题描述

init给定图的初始化，mMap值为0表示无障碍，1表示有障碍。

add，增加的加油站station，加油可以行驶init的mRange距离。

然后求最短距离，mFrom到mTo（对应add函数的mId）。

下面是
我写的算法，还能优化吗？一只超时。

import java.util.*;
 
class UserSolution
{
 
    class Node implements Comparator<Node> {
 
        int id;
        int x;
        int y;
        int dist;
 
        public Node() {}
 
        public Node(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
 
        public Node(int id, int x, int y) {
            this.id = id; // -1 白色， -2 灰色（障碍物）
            this.x = x;
            this.y = y;
        }
 
        public Node(int id, int x, int y, int dist) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
 
        @Override
        public int compare(Node o1, Node o2) {
            return o1.dist - o2.dist;
        }
    }
 
 
    int n;
    int[][] graph;
    HashMap<Integer, Node> nodeMap = new HashMap<>();
    HashMap<Integer, ArrayList<Node>> adjTable = new HashMap<>();
    int range;
 
    int[] dx = new int[]{1, -1, 0, 0};
    int[] dy = new int[]{0, 0, 1, -1};
 
    void init(int N, int mRange, int mMap[][])
    {
        this.n = N;
        this.graph = new int[n][n];
        nodeMap.clear();
        adjTable.clear();
        this.range = mRange;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mMap[i][j] == 0) {
                    graph[i][j] = -1;
                    continue;
                }
                if (mMap[i][j] == 1) {
                    graph[i][j] = -2;
                }
            }
        }
    }
 
    void add(int mID, int mRow, int mCol)
    {
        Node insertNode = new Node(mID, mRow, mCol);
        nodeMap.put(mID, insertNode);
        graph[mRow][mCol] = mID;
 
        adjTable.put(mID, new ArrayList<>());
 
        update(insertNode);
 
    }
 
    private void update(Node updateNode) {
 
        ArrayDeque<Node> queue = new ArrayDeque<>();
        boolean[][] vis = new boolean[n][n];
 
        queue.add(new Node(updateNode.id, updateNode.x, updateNode.y, 0));
        vis[updateNode.x][updateNode.y] = true;
 
        while (!queue.isEmpty()) {
 
            Node startNode = queue.poll();
 
            for (int i = 0; i < 4; i++) {
 
                int newX = startNode.x + dx[i];
                int newY = startNode.y + dy[i];
                int dist = startNode.dist + 1;
                if (!isOut(newX, newY)) {
                    continue;
                }
                int id = graph[newX][newY];
 
 
                if (isOut(newX, newY) && !vis[newX][newY] && id > -2 && dist <= range) {
                    vis[newX][newY] = true;
 
                    queue.add(new Node(id, newX, newY, dist));
 
                    if (id >= 0) {
                        adjTable.get(updateNode.id).add(new Node(id, newX, newY, dist));
                        adjTable.get(id).add(new Node(updateNode.id, updateNode.x, updateNode.y, dist));
                    }
                }
 
            }
 
        }
 
 
    }
 
    private boolean isOut(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < n;
    }
 
 
    int distance(int mFrom, int mTo)
    {
 
        Node sourceNode = nodeMap.get(mFrom);
        Node targetNode = nodeMap.get(mTo);
        if (sourceNode == null || targetNode == null) {
            return -1;
        }
 
        PriorityQueue<Node> queue = new PriorityQueue<>(new Node());
        boolean[] vis = new boolean[205];
        vis[mFrom] = true;
 
        queue.add(new Node(sourceNode.id,0));
 
        while (!queue.isEmpty()) {
 
            Node startNode = queue.poll();
            vis[startNode.id] = true;
            if (startNode.id == mTo) {
                return startNode.dist;
            }
 
 
            for (Node node : adjTable.get(startNode.id)) {
                if (!vis[node.id]) {
                    queue.add(new Node(node.id, node.dist + startNode.dist));
                }
            }
        }
 
            return -1;
    }
}

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码中，已经实现了一个基本的广度优先搜索(BFS)算法来解决从一个节点到另一个节点的最短路径问题。然而，这个实现有一些可以优化的地方。以下是针对您的代码进行的一些优化建议：

1. 合并更新与搜索：将update方法中的逻辑融入到distance方法中。这样可以减少数据结构的使用，提高效率。

2. 使用HashSet替代boolean数组：使用HashSet替换二维布尔数组vis，以减少空间复杂度，并且查找速度更快。

3. 使用双向边：当添加新节点时，确保同时将边加入到邻接表的两个方向，这样可以在搜索阶段减少查询次数。

4. 优化队列结构：使用一个优先队列（基于堆的数据结构），这样可以直接获取最小距离的节点，而不需要每次迭代都遍历整个队列。

5. 优化距离计算：在添加新节点到队列时，只需存储目标节点的距离，而不是从源节点到目标节点的总距离，这会简化代码并加快搜索过程。

以下是优化后的代码：

import java.util.*;

class UserSolution {

    class Node implements Comparable<Node> {
        int id;
        int x;
        int y;

        public Node() {}

        public Node(int id) {
            this.id = id;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.x, other.x);
        }
    }

    int n;
    int[][] graph;
    HashMap<Integer, Node> nodeMap = new HashMap<>();
    HashMap<Integer, HashSet<Node>> adjTable = new HashMap<>();
    int range;

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};

    void init(int N, int mRange, int[][] mMap) {
        this.n = N;
        this.graph = new int[n][n];
        nodeMap.clear();
        adjTable.clear();
        this.range = mRange;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (mMap[i][j] == 0) {
                    graph[i][j] = -1;
                    continue;
                }
                if (mMap[i][j] == 1) {
                    graph[i][j] = -2;
                }
            }
        }
    }

    void add(int mID, int mRow, int mCol) {
        Node insertNode = new Node(mID);
        nodeMap.put(mID, insertNode);
        graph[mRow][mCol] = mID;

        adjTable.putIfAbsent(mID, new HashSet<>());
        adjTable.get(mID).add(insertNode);

        for (int i = 0; i < 4; i++) {
            int newX = mRow + dx[i];
            int newY = mCol + dy[i];
            if (isInBounds(newX, newY) && graph[newX][newY] != -2 && graph[newX][newY] > -1) {
                adjTable.get(graph[newX][newY]).add(insertNode);
                adjTable.get(mID).add(new Node(graph[newX][newY]));
            }
        }
    }

    private boolean isInBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < n;
    }

    int distance(int mFrom, int mTo) {
        Node sourceNode = nodeMap.get(mFrom);
        Node targetNode = nodeMap.get(mTo);
        if (sourceNode == null || targetNode == null) {
            return -1;
        }

        PriorityQueue<Node> queue = new PriorityQueue<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.offer(sourceNode);
        visited.add(mFrom);

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();

            if (currentNode.id == mTo) {
                return currentNode.x;
            }

            for (Node neighbor : adjTable.get(currentNode.id)) {
                if (!visited.contains(neighbor.id)) {
                    queue.offer(neighbor);
                    visited.add(neighbor.id);
                }
            }
        }

        return -1;
    }
}

这些修改应该能提升算法性能，但请注意，对于非常大的图，可能仍然需要考虑更高效的算法，比如A*搜索或者Dijkstra算法，特别是当存在启发式信息时。