仅返回实际最短路径中的顶点 [英] Returning only the vertices in the actual shortest path

问题描述

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

I know the title is a bit messy, but I don't know how to explain it better.

我正在尝试做什么：

使用文本文件中的图形，找到并打印从顶点A到顶点B的最短路径（最小顶点数量）。

Using a graph found in a text file, find and print the shortest path (minimum amount of vertices) from vertex A to vertex B.

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

Note: using breadth-first search, not Dijkstra's.

我得到了什么：

一种在图表上应用BFS的工作算法，但没有好方法实际打印出最短路径。

A working algorithm that applies BFS on the graph, but no good way of actually printing out the shortest path.

我很难区分最短路径中的顶点与仅通过算法运行的顶点，但不是最短路径中的顶点。

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

For example: Find the shortest path between 0 and 4. 0 connects to 1,2 and 3. 1 connects to 4. My path turns out to be [0,1,2,3,4] instead of [0,1,4].

我一直无法找到任何询问相同问题的线程，或任何行走第粗略的BFS，包括这个，所以我不确定我是否正在使这个方式比它更难？

I haven't been able to find any threads asking the same question, or any walk-through of BFS that includes this, so I'm not sure if I'm making this out to be way harder than it is?

编辑代码可能会让您感兴趣（如果我避免使用圈子，则根本不确定？）

code for those who may be interested (not sure at all if I'm avoiding circles?)

编辑2： 更改了将路径存储到堆栈的方式。

Edit 2: Changed the way I store my path to a 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());
        }
    }
}

对变量和方法的一些解释：

Some explanation of variables and methods:

v =原点顶点

w =目标顶点

g = graph

g = graph

vi =迭代v的邻居的正常迭代器

vi = a normal iterator that iterates over the neighbours of v

感谢阅读！

推荐答案

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

You will have to have specific path field for each vertex. That way you can keep track of the paths you've chosen, hence the short path found. I will use an String array, just like you used the Boolean array for storing visited vertices.

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

这篇关于仅返回实际最短路径中的顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！