无向图中从源节点到所有节点的最短路径优化问询

输入为二维数组[][]edges，每一行代表无向图的一条双向边，需要计算从特定节点（如节点0）到所有节点的最短距离。现有代码可正常运行，但存在重复计算问题：多次调用computeDistPerNode(m,0,key)时，会重复执行BFS流程，浪费计算资源，需要优化以复用计算结果。

原代码如下：

public Map<Integer, List<Integer>> createUnDirectedGraph(int [][]edges) {
    Map<Integer, List<Integer>> m = new HashMap<>();
    for(var i = 0; i<edges.length; i++) {
        m.put(edges[i][0], new ArrayList<>());
        m.put(edges[i][1], new ArrayList<>());
    }
    for(var edge:edges) {
        var v1 = edge[0];
        var v2 = edge[1];
        m.get(v1).add(v2);
        m.get(v2).add(v1);
    }
    return m;
}

public int[] getShortestDistances(Map<Integer, List<Integer>> m) {
    int distance[] = new int[m.size()];
    for(Integer key:m.keySet()) {
       var d = computeDistPerNode(m,0,key);
       distance[key] = d;
    }
    return distance;
}
public int computeDistPerNode(Map<Integer, List<Integer>> m, int src, int dest) {
    Queue<Integer> q = new LinkedList<>();
    Integer dist[] = new Integer[m.size()];
    Set<Integer> visited = new HashSet<>();
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    q.add(src);
    while(!q.isEmpty()) {
       var currNode = q.poll();
       if(visited.contains(currNode)) continue;
       visited.add(currNode);
       if(currNode == dest) {
           return dist[dest];
       }

       for(var child: m.get(currNode)) {
           if (visited.contains(child)) {
               continue;
           }

           q.offer(child);
           var newDist = 1 + dist[currNode];
           if(newDist<dist[child]) {
               dist[child] = newDist;
           }
       }
    }
    return -1;
}

public int[][] getsample() {
    int [][] edges = {
            {0,1},
            {0,2},
            {1,4},
            {2,3},
            {4,3},
            {0,4},
    };
    return edges;
}

原代码的核心问题是重复执行BFS：每次调用computeDistPerNode都会从源节点重新启动一次BFS，只为获取单个目标节点的距离。实际上，BFS的特性就是从源节点出发，遍历过程中可以一次性计算出所有节点的最短距离，完全不需要多次执行。

优化方案：重写距离计算逻辑，让BFS只执行一次，直接返回所有节点到源节点的距离数组，后续直接复用这个数组即可。

public Map<Integer, List<Integer>> createUnDirectedGraph(int [][]edges) {
    Map<Integer, List<Integer>> m = new HashMap<>();
    for(var i = 0; i<edges.length; i++) {
        m.put(edges[i][0], new ArrayList<>());
        m.put(edges[i][1], new ArrayList<>());
    }
    for(var edge:edges) {
        var v1 = edge[0];
        var v2 = edge[1];
        m.get(v1).add(v2);
        m.get(v2).add(v1);
    }
    return m;
}

// 优化后的方法：一次BFS计算所有节点到源节点的最短距离
public int[] computeAllShortestDistances(Map<Integer, List<Integer>> m, int src) {
    int nodeCount = m.size();
    int[] dist = new int[nodeCount];
    // 初始化距离为-1（表示未可达），源节点距离为0
    Arrays.fill(dist, -1);
    dist[src] = 0;
    
    Queue<Integer> q = new LinkedList<>();
    q.add(src);
    
    while(!q.isEmpty()) {
        int currNode = q.poll();
        // 遍历当前节点的所有邻接节点
        for(int neighbor : m.get(currNode)) {
            // 如果邻接节点未被访问过（距离为-1）
            if(dist[neighbor] == -1) {
                dist[neighbor] = dist[currNode] + 1;
                q.offer(neighbor);
            }
        }
    }
    return dist;
}

// 直接调用一次优化后的方法即可得到所有距离
public int[] getShortestDistances(Map<Integer, List<Integer>> m) {
    return computeAllShortestDistances(m, 0);
}

public int[][] getsample() {
    int [][] edges = {
            {0,1},
            {0,2},
            {1,4},
            {2,3},
            {4,3},
            {0,4},
    };
    return edges;
}

1. 减少BFS执行次数：从原来的节点数次BFS减少到1次，时间复杂度从O(N*(V+E))优化为O(V+E)（V是节点数，E是边数），性能大幅提升。
2. 简化逻辑：去掉了原computeDistPerNode中针对单个目标节点的提前返回逻辑，改为完整遍历所有节点，一次性生成所有距离。
3. 更清晰的状态标记：用dist数组的-1值标记未访问节点，省去了单独的visited集合，逻辑更简洁。

内容的提问来源于stack exchange，提问作者curiousengineer