我试图建立它返回一个未加权的曲线图从一个节点到另一个的最短路径的方法。 我认为使用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;
}
其实你的代码将无法在循环图完成，考虑图表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;
}
谢谢Giolekva！
我重写了它，重构了一些：
- 访问节点的集合并不一定是一个地图。
- 对于重构路径，下一个节点可以抬起头来，前面的节点，而不是，省去了扭转方向的需要。
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;
}
这实在是再简单得到的答案只是一个比所有对对。 计算最短路径的常用方法是开始喜欢你这样做，但要每次遇到一个新的节点的说明，并记录路径上的一个节点。 然后，当你到达目标节点，你可以按照反向链接的来源和获取路径。 因此，除去directions.add(current)从循环，并添加代码类似如下
Map<Node,Node> backlinks = new HashMap<Node,Node>();
在一开始，然后在环
if (!backlinks.containsKey(node)) {
backlinks.add(node, current);
q.add(node);
}
然后到了最后，只是构建了directions使用向后名单backlinks映射。
通过你的每执行一次循环，你打电话
directions.Add(current);
相反，你应该移到那一个地方，你真的知道你想要的条目。
您必须包括对每个节点的父节点，当你把它们放在你的队列中。 然后，你可以递归读取从列表中选择路径。
假设你想找到从A到d在此图中的最短路径：
/B------C------D
/ |
A /
\ /
\E---------
每次排队节点时间，跟踪你有来这里的路上。 因此，在步骤1 B（A）E（A）被放置在队列中。 在步骤两个B被移出队列和C（B）被放在队列等，其则容易再次找到自己的方式，仅通过递归“倒退”。
最好的办法可能是让一个数组，只要有节点，并保持连接是有，（这是什么通常即做的Dijkstra）。
