java - 仅返回实际最短路径中的顶点

Question

我知道标题有点乱，但我不知道如何更好地解释它。

我正在尝试做的事情:

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

注意:使用广度优先搜索，而不是 Dijkstra 的。

我得到的:

一种在图上应用 BFS 的可行算法，但没有真正打印出最短路径的好方法。

我很难区分最短路径中的顶点与简单地通过算法运行但不在最短路径中的顶点。

例如:求0到4之间的最短路径。0 连接到 1,2 和 3。1 连接到 4。我的路径原来是 [0,1,2,3,4] 而不是 [0,1,4]。

我还没有找到任何提出相同问题的线程，也没有找到任何包含此问题的 BFS 演练，所以我不确定我是否正在做这个方式 比现在更难？

编辑:代码供可能感兴趣的人使用(完全不确定我是否在避开圈子？)

编辑 2: 更改了我将路径存储到 Stack 的方式。

public String findPath(int v, int w) {
    Queue<Integer> q = new LinkedList<Integer>();
    boolean[] visited = new boolean[g.numVertices()];

    q.add(v);
    Stack<Integer> path = new Stack<Integer>();
    while(q.peek() != null) {
        runBFS(q.poll(),w,visited,q,path);
    }
    return path.toString();
} 

private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
    if(visited[v]) {
    }
    else if(v == w) {
        path.add(v);
        q.clear();
    }
    else {
        path.add(v);
        visited[v] = true;
        VertexIterator vi = g.adjacentVertices(v);
        while(vi.hasNext()) {
                q.add(vi.next());
        }
    }
}

变量和方法的一些解释:

v = 原点

w = 目标顶点

g = 图

vi = 迭代 v 的邻居的普通迭代器

感谢阅读!

Answer 1

您必须为每个顶点设置特定的路径字段。这样你就可以跟踪你选择的路径，从而找到最短的路径。我将使用一个字符串数组，就像您使用 boolean 数组存储访问过的顶点一样。

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