Java 未加权图的最短路径（最少节点）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1579399/
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
Shortest path (fewest nodes) for unweighted graph
提问by Robert
I'm trying build a method which returns the shortest path from one node to another in an unweighted graph. I considered the use of Dijkstra's but this seems a bit overkill since I only want one pair. Instead I have implemented a breadth-first search, but the trouble is that my returning list contains some of the nodes that I don't want - how can I modify my code to achieve my goal?
我正在尝试构建一种方法，该方法返回未加权图中从一个节点到另一个节点的最短路径。我考虑过使用 Dijkstra 的，但这似乎有点矫枉过正，因为我只想要一对。相反，我实现了广度优先搜索，但问题是我的返回列表包含一些我不想要的节点 - 如何修改我的代码以实现我的目标？
public List<Node> getDirections(Node start, Node finish){
List<Node> directions = new LinkedList<Node>();
Queue<Node> q = new LinkedList<Node>();
Node current = start;
q.add(current);
while(!q.isEmpty()){
current = q.remove();
directions.add(current);
if (current.equals(finish)){
break;
}else{
for(Node node : current.getOutNodes()){
if(!q.contains(node)){
q.add(node);
}
}
}
}
if (!current.equals(finish)){
System.out.println("can't reach destination");
}
return directions;
}
采纳答案by giolekva
Actually your code will not finish in cyclic graphs, consider graph 1 -> 2 -> 1. You must have some array where you can flag which node's you've visited already. And also for each node you can save previous nodes, from which you came. So here is correct code:
实际上，您的代码不会在循环图中完成，请考虑图 1 -> 2 -> 1。您必须有一些数组，您可以在其中标记您已经访问过的节点。而且对于每个节点，您还可以保存您来自的先前节点。所以这里是正确的代码：
private Map<Node, Boolean>> vis = new HashMap<Node, Boolean>();
private Map<Node, Node> prev = new HashMap<Node, Node>();
public List getDirections(Node start, Node finish){
List directions = new LinkedList();
Queue q = new LinkedList();
Node current = start;
q.add(current);
vis.put(current, true);
while(!q.isEmpty()){
current = q.remove();
if (current.equals(finish)){
break;
}else{
for(Node node : current.getOutNodes()){
if(!vis.contains(node)){
q.add(node);
vis.put(node, true);
prev.put(node, current);
}
}
}
}
if (!current.equals(finish)){
System.out.println("can't reach destination");
}
for(Node node = finish; node != null; node = prev.get(node)) {
directions.add(node);
}
directions.reverse();
return directions;
}
回答by John Fisher
Every time through your loop, you call
每次通过你的循环，你打电话
directions.Add(current);
Instead, you should move that to a place where you really know you want that entry.
相反，您应该将其移至您真正知道您想要该条目的地方。
回答by JaakkoK
It is really no simpler to get the answer for just one pair than for all the pairs. The usual way to calculate a shortest path is to start like you do, but make a note whenever you encounter a new node and record the previous node on the path. Then, when you reach the target node, you can follow the backlinks to the source and get the path. So, remove the directions.add(current)from the loop, and add code something like the following
仅获得一对的答案并不比获得所有对的答案更简单。计算最短路径的常用方法是像您一样开始，但是每当遇到新节点时记下并记录路径上的前一个节点。然后，当您到达目标节点时，您可以按照指向源的反向链接并获取路径。因此，directions.add(current)从循环中删除，并添加如下代码
Map<Node,Node> backlinks = new HashMap<Node,Node>();
in the beginning and then in the loop
在开始然后在循环中
if (!backlinks.containsKey(node)) {
backlinks.add(node, current);
q.add(node);
}
and then in the end, just construct the directionslist in backwards using the backlinksmap.
然后最后，只需directions使用backlinks地图向后构造列表。
回答by JaakkoK
You must include the parent node to each node when you put them on your queue. Then you can just recursively read the path from that list.
当您将它们放入队列时，您必须将父节点包含到每个节点中。然后你可以递归地从该列表中读取路径。
Say you want to find the shortest path from A to D in this Graph:
假设您想在此图中找到从 A 到 D 的最短路径：
/B------C------D
/ |
A /
\ /
\E---------
Each time you enqueue a node, keep track of the way you got here. So in step 1 B(A) E(A) is put on the queue. In step two B gets dequeued and C(B) is put on the queue etc. Its then easy to find your way back again, by just recursing "backwards".
每次将节点加入队列时，请跟踪您到达此处的方式。所以在步骤 1 B(A) E(A) 被放入队列。在第二步中，B 出列，C(B) 被放入队列等。然后很容易找到返回的路，只需“向后”递归。
Best way is probably to make an array as long as there are nodes and keep the links there, (which is whats usually done in ie. Dijkstra's).
最好的方法可能是制作一个数组，只要有节点并保持链接在那里，（这是通常在 ie.Dijkstra's 中所做的）。
回答by Leif Bork
Thank you Giolekva!
谢谢焦列克瓦！
I rewrote it, refactoring some:
我重写了它，重构了一些：
- The collection of visited nodes doesn't have to be a map.
- For path reconstruction, the next node could be looked up, instead of the previous node, eliminating the need for reversing the directions.
- 访问节点的集合不一定是地图。
- 对于路径重建，可以查找下一个节点，而不是前一个节点，从而无需反转方向。
public List<Node> getDirections(Node sourceNode, Node destinationNode) {
//Initialization.
Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
Node currentNode = sourceNode;
//Queue
Queue<Node> queue = new LinkedList<Node>();
queue.add(currentNode);
/*
* The set of visited nodes doesn't have to be a Map, and, since order
* is not important, an ordered collection is not needed. HashSet is
* fast for add and lookup, if configured properly.
*/
Set<Node> visitedNodes = new HashSet<Node>();
visitedNodes.add(currentNode);
//Search.
while (!queue.isEmpty()) {
currentNode = queue.remove();
if (currentNode.equals(destinationNode)) {
break;
} else {
for (Node nextNode : getChildNodes(currentNode)) {
if (!visitedNodes.contains(nextNode)) {
queue.add(nextNode);
visitedNodes.add(nextNode);
//Look up of next node instead of previous.
nextNodeMap.put(currentNode, nextNode);
}
}
}
}
//If all nodes are explored and the destination node hasn't been found.
if (!currentNode.equals(destinationNode)) {
throw new RuntimeException("No feasible path.");
}
//Reconstruct path. No need to reverse.
List<Node> directions = new LinkedList<Node>();
for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
directions.add(node);
}
return directions;
}
