未加权图的最短路径(最小节点)
我正在尝试构建一种方法,该方法在未加权图中返回从一个节点到另一个节点的路径" title="最短路径">最短路径。我考虑过使用Dijkstra的方法,但这似乎有点矫kill过正,因为我只想要一对。相反,我实现了广度优先搜索,但是麻烦的是我的返回列表包含一些我不想要的节点-
如何修改代码以实现目标?
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。您必须具有一些数组,可以在其中标记已访问过的节点。并且对于每个节点,您可以保存您来自的先前节点。所以这是正确的代码:
私有Map <Node,Boolean >> vis = new HashMap <Node,Boolean>();私有Map <Node,Node> prev = new HashMap <Node,Node>();
公开列表getDirections(节点开始,节点完成){
列表方向=新的LinkedList();
队列q = new LinkedList();
节点电流=开始;
q.add(当前);
vis.put(current,true);
while(!q.isEmpty()){
当前= q.remove();
如果(current.equals(finish)){
打破;
}其他{
for(节点节点:current.getOutNodes()){
if(!vis.contains(node)){
q.add(node);
vis.put(node,true);
prev.put(节点,当前);
}
}
}
}
如果(!current.equals(finish)){
System.out.println(“无法到达目的地”);
}
for(Node node = finish; node!= null; node = prev.get(node)){
directions.add(node);
}
directions.reverse();
返回指示;
}
以上是 未加权图的最短路径(最小节点) 的全部内容, 来源链接: utcz.com/qa/402808.html