我有一个输入为[][]edges
的数组。数组的列长度为2。因此,2D数组的每一行都有2个元素。每个元素都是一个顶点。它是双向的,即我们可以说边是双向的。因此,如果我们遍历这个2D数组,我们可以说我们有一个无向图。
我正在尝试找到从一个
特定节点到所有节点的最短距离。在这种情况下,从节点0
到存在的所有节点。
我有一个可行的代码,但我认为我正在重新计算我想要避免的东西。我一遍又一遍地调用函数computeDistPerNode(m,0,key);
,我确信它正在重新计算从0
到之前调用中看到的节点的距离。我无法对其进行优化并利用过去的计算。我该怎么做?
以下是未经优化的工作代码
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;
}
if(newDist < dist[child]) {
的原因是因为visited会自然地处理它,如果没有访问过,则newDist始终较小?您能帮我理解一下吗?如何在没有该检查的情况下,可能不会将较大的newDist值写入当前的dist[child]中?我认为原因是由于BFS /使用队列的性质,当未访问的节点被拉出时,子节点将首先被访问,因此不需要进行检查? - curiousengineer