java 仅返回实际最短路径中的顶点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5463505/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Returning only the vertices in the actual shortest path
提问by bjrnt
I know the title is a bit messy, but I don't know how to explain it better.
我知道标题有点乱，但我不知道如何更好地解释它。
What I'm trying to do:
我正在尝试做的事情：
Using a graph found in a text file, find and print the shortest path (minimum amount of vertices) from vertex A to vertex B.
使用在文本文件中找到的图形，找到并打印从顶点 A 到顶点 B 的最短路径（最少顶点数）。
Note: using breadth-first search, not Dijkstra's.
注意：使用广度优先搜索，而不是 Dijkstra。
What I've got:
我有什么：
A working algorithm that applies BFS on the graph, but no good way of actually printing out the shortest path.
一种在图形上应用 BFS 的工作算法，但没有实际打印出最短路径的好方法。
I'm having a hard time distinguishing a vertex in the shortest path from one that is simply run through the algorithm, but not in the shortest path.
我很难将最短路径中的顶点与仅通过算法运行但不在最短路径中的顶点区分开来。
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].
例如：找到0到4之间的最短路径。0连接到1,2和3。1连接到4。我的路径结果是[0,1,2,3,4]而不是[0,1， 4]。
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 wayharder than it is?
我一直没能找到任何线程问同样的问题，或步行通过BFS的，包括这一点，所以我不知道如果我做了这一点，是这样难度比它是什么？
Edit:code for those who may be interested (not sure at all if I'm avoiding circles?)
编辑：那些可能感兴趣的人的代码（完全不确定我是否在避免圈子？）
Edit 2:Changed the way I store my path to a Stack.
编辑 2：更改了我将路径存储到堆栈的方式。
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 = vertex of origin
v = 原点顶点
w = target vertex
w = 目标顶点
g = graph
g = 图
vi = a normal iterator that iterates over the neighbours of v
vi = 迭代 v 的邻居的普通迭代器
Thanks for reading!
谢谢阅读！
回答by jCoder
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;
}
回答by pbos
Another compact (space-wise) solution that us assistants have suggested and doesn't use O(n^2) storage space is to have each node store only which node it came from. This can be done by changing the visited-list to an integer array (int[] visited).
我们助手建议的另一个紧凑（空间方面）解决方案不使用 O(n^2) 存储空间是让每个节点只存储它来自哪个节点。这可以通过将访问列表更改为整数数组 ( int[] visited) 来完成。
step 1: initialize visited list, so that every element is '-1', or "unvisited"
第 1 步：初始化访问列表，以便每个元素都是'-1'，或“未访问”
step 2: mark the first node as visited by itself visited[v] = v;
步骤2：将第一个节点标记为自己访问过 visited[v] = v;
Do a BFS (like you do, with the following modifications:)
做一个 BFS（像你一样，做了以下修改：）
when moving from v -> v_next:
当从 v -> v_next 移动时：
if(visited[v_next] == -1)
{
visited[v_next] = v;
q.put(v_next);
}
// else skip it, it's already been visited
This way, if w is reachable, visited[w] will store which node it came from, from that node, you can backtrack all the way back to v and finally print them in the opposite order. (This is done either using a stack or a recursive print method.)
这样，如果 w 可达，visited[w] 将存储它来自哪个节点，从那个节点，你可以一直回溯到 v，最后以相反的顺序打印它们。（这是使用堆栈或递归打印方法完成的。）
Hope that makes sense. :)
希望这是有道理的。:)
回答by thkala
When you store a vertex in the BFS queue, you also need to store a copy of the path through which it has been reached, so that it will be available once that vertex is dequeued. As it is now, your code does not keep any kind of path information on the queued vertices - it only keeps a list of the nodes it visits.
当您在 BFS 队列中存储一个顶点时，您还需要存储一个到达它的路径的副本，以便在该顶点出队后可以使用它。就像现在一样，您的代码不会在排队的顶点上保留任何类型的路径信息 - 它只保留它访问的节点的列表。
You could, for example, use a separate queue that will be processed in parallel, in which you will store the current path, and then restore it once you dequeue the next vertex to search.
例如，您可以使用将并行处理的单独队列，您将在其中存储当前路径，然后在将要搜索的下一个顶点出列后将其恢复。
回答by regularfry
You need to push your current node onto a stack, and only print the whole stack out once you reach the destination.
您需要将当前节点推入堆栈，并且只有在到达目的地后才将整个堆栈打印出来。
