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;
}

你可以一次性计算从源节点到所有其他节点的距离。
方法 `int computeDistPerNode(Map<Integer, List<Integer>> m, int src, int dest)` 在到达目标节点时立即返回。将其改为在队列为空时返回 `dist` 数组。以下是修改后的方法：
```java
public Integer[] computeDistFromSource(Map<Integer, List<Integer>> m, int src) {
    Set<Integer> visited = new HashSet<>();
    Integer[] dist = new Integer[m.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Queue<Integer> q = new LinkedList<>();
    visited.add(src);   // 在此处标记源节点为已访问
    q.add(src);
    while(!q.isEmpty()) {
        var currNode = q.poll();
        for(var child: m.get(currNode)) {
            if (!visited.contains(child)) {
                visited.add(child);
                q.offer(child);
                dist[child] = 1 + dist[currNode];
            }
        }
    }
    return dist;
}

public Integer[] computeDistFromSource(Map<Integer, List<Integer>> m, int src) {
    Set<Integer> visited = new HashSet<>();
    Integer[] dist = new Integer[m.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    Queue<Integer> q = new LinkedList<>();
    visited.add(src);   // 在此处标记源节点为已访问
    q.add(src);
    while(!q.isEmpty()) {
        var currNode = q.poll();
        for(var child: m.get(currNode)) {
            if (!visited.contains(child)) {
                visited.add(child);
                q.offer(child);
                dist[child] = 1 + dist[currNode];
            }
        }
    }
    return dist;
}

0 ------- 1
|\        |
|  \      |
|    \    | 
|      \  |
|        \|
|         4
|         |
|         |
|         |
2 ------- 3

<details>
<summary>英文:</summary>
You can calculate distance from the source node to all the other nodes in one go. 
The method `int computeDistPerNode(Map&lt;Integer, List&lt;Integer&gt;&gt; m, int src, int dest)` returns as soon as you reach the destination node. Change that to return the `dist` array when the queue is empty. Here is your modified method

Integer[] dist = new Integer[m.size()];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(src);
while(!q.isEmpty()) {
var currNode = q.poll();
if(visited.contains(currNode)) continue;
visited.add(currNode);
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 dist;

## Improvements
If you re-position your lines a little, you can avoid three if calls. This results in a more clean and readable code.

Integer[] dist = new Integer[m.size()];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
Queue<Integer> q = new LinkedList<>();
visited.add(src);   // mark source visited here
q.add(src);
while(!q.isEmpty()) {
var currNode = q.poll();
for(var child: m.get(currNode)) {
if (!visited.contains(child)) {
visited.add(child);
q.offer(child);
dist[child] = 1 + dist[currNode];
}
}
}
return dist;

## Analysis
The algorithm employed is [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search). According to [Wikipedia](https://en.wikipedia.org/wiki/Breadth-first_search#Time_and_space_complexity)
> The time complexity can be expressed as `O(|V| + |E|)`, since every vertex and every edge will be explored in the worst case. `|V|` is the number of vertices and `|E|` is the number of edges in the graph. Note that `O(|E|)` may vary between `O(1)` and `O(|V|^2)`, depending on how sparse the input graph is.
## Question
> Can you help me understand how a larger value of newDist might not get written in current dist[child] without that check? I think the reason is that a child due to the nature of BFS/using queue will be visited first when an univisited node is pulled out and hence the check is not required?
The `if(newDist < dist[child])` condition is necessary in your code for correct working. It is not required in the optimized code. The reason is the placement of `visited.add(child)`. In your code, that check happens after a node is polled from queue. In the optimized code, this happens immediately after a node is discovered. This creates a big difference.
Consider your input graph

##### Working of your code
The source vertex is 0. Before the beginning of the loop `while (!q.isEmpty()` we add it to the queue.
In the while loop, we remove 0 and mark it as visited. We explore its neighbors 1, 2 and 4 in that order. We update their distance to 1 and add all of them to the queue. *However, none of them have been marked as visited.* 
Now we go back to the start of the while loop, poll 1, mark it as visited and again explore its neighbors 0 and 4. We do not update the distance of 0 since it is visited. *We add 4 to the queue again even though it is already part of the queue.* We have added the same node in the queue again this is not a good thing in itself. *Notice if there is no `if(newDist < dist[child])` condition, its distance will be updated to 2 which is wrong.*
##### Working of the optimized code
The source vertex is 0. Before the beginning of the loop `while (!q.isEmpty()` we add it to queue and mark it as visited here only.
In the while loop, we remove 0. We explore its neighbors 1, 2 and 4 in that order. We update their distance to 1 and add all of them to the queue and mark all of them as visited. *Hence their distance can never be updated again.*
Now we go back to the start of the while loop, poll 1 and again explore its neighbors 0 and 4. We do not update the distance of 0 as well as 1 since both of them are visited. The node 4 is also not added to the queue twice.
</details>
# 答案2
**得分**: 1
如果您使用`min-priority-queue`或`min-heap`，您可以将算法复杂度降低到`O(|V| * |E|)`，即顶点数和边数的乘积。即使在从@AKSingh的[答案](https://stackoverflow.com/a/76298775/1202808)中改进了您的算法之后，我认为它仍然是`O(|V|^2)`。
维基百科对[Dijkstra算法](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)有一个很好的描述，这是解决使用`min-priority-queue`解决最短路径问题的标准技术。[这里](https://takeuforward.org/data-structure/dijkstras-algorithm-using-priority-queue-g-32/)有一个更教程导向的描述，其中包含很多图示，以可视化算法。
以下是实现该算法的一些示例代码。我很抱歉它不是用`Java`编写的，但翻译应该很简单。
示例代码
-----------
```c++
#include &lt;iostream&gt;
#include &lt;map&gt;
#include &lt;queue&gt;
#include &lt;set&gt;
#include &lt;vector&gt;
using NodePair = std::pair&lt;int,int&gt;;
using NodePairs = std::vector&lt;NodePair&gt;;
using DistanceVertex = std::pair&lt;int, int&gt;;
using MinQueue = std::priority_queue&lt;DistanceVertex,
std::vector&lt;DistanceVertex&gt;,
std::greater&lt;DistanceVertex&gt;&gt;;
int main(int argc, const char *argv[]) {
// 示例问题。我们将图存储为邻接列表
// 使用multimap。
std::multimap&lt;int, int&gt; edges {
{ 0, 1 },
{ 0, 2 },
{ 1, 4 },
{ 2, 3 },
{ 4, 3 },
{ 0, 4 }
};
// 有多少个顶点？
int max_vertex{};
for (auto [a, b] : edges) {
max_vertex = std::max(max_vertex, a);
max_vertex = std::max(max_vertex, b);
}
int number_vertices = max_vertex + 1;
// 将源到每个顶点的距离初始化为MAX_INT。
int source{};
std::vector&lt;int&gt; distance(number_vertices, std::numeric_limits&lt;int&gt;::max());
// 初始化到源的距离和优先队列
MinQueue pq;
distance[source] = 0;
pq.emplace(0, source);
while (!pq.empty()) {
auto [udist, udx] = pq.top();
pq.pop();
// 遍历vdx的所有邻居
auto [begin, end] = edges.equal_range(udx);
for (auto iter = begin; iter != end; ++iter) {
auto vdx = iter-&gt;second, vdist = iter-&gt;first;
// 如果存在更短的路径，则记录它
if (udist + vdist &lt; distance[vdx]) {
distance[vdx] = udist + vdist;
pq.push({udist, vdx});
}
}
}
// distance现在包含源和每个节点之间的最短距离
for (auto i = 0; i &lt; number_vertices; ++i)
std::cout &lt;&lt; distance[i] &lt;&lt; std::endl;
return 0;
}