用2个队列求2d矩阵的最短路径

Question

我想做的:

使用在文本文件中找到的图形，找到并打印从顶点a到顶点b的最短路径(顶点数量最少)

当前实现:

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];
    String[] pathTo = new String[g.numVertices()];
    q.add(v);
    pathTo[v] = v+" ";
    while(q.peek() != null) {
        if(runBFS(q.poll(),w,visited,q,pathTo))
        break;
    }
    return pathTo[w];
}
private boolean runBFS(int v, int w, boolean[] visited, Queue<Integer> q, String[] pathTo) {
    if(visited[v]) {
    }
    else if(v == w)
        return true; 
    }
    else {
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
            int nextVertex = vi.next();
            pathTo[nextVertex] = pathTo[v] + nextVertex + " ";
            q.add(nextVertex);
        }
    }
    return false;
}

v =原点

w =目标顶点

g = graph

vi =一个普通迭代器，迭代v

的相邻节点

现在，它正在使用String[]来跟踪路径，但我建议有一个解决方案可以使用Queue<ArrayList<Integer>>而不是String[]，通过与q队列并行运行此队列来保存路径。

谁能指点我一下?

Answer 1

您可以使用第二个队列Queue<ArrayList<Integer>> q2以相同的顺序存储从v到当前q中的每个节点的最短路径(作为ArrayList<Integer>)。每当轮询q时，也轮询q2，每当向q添加节点时，通过将最短路径复制到前一个节点并附加当前节点来计算到该节点的最短路径，并将其添加到q2。

然而，请注意，复制最短路径可能会在顶点数量上花费线性时间，这将增加总体复杂性。出于这个原因，我不推荐这种方法。相反，对于每个节点n，您可以存储访问n时的前一个节点。一旦到达目标节点w，您就可以通过这些前一个节点回溯以找到从开始节点开始的最短路径。