我正在尝试构建一种方法,该方法在未加权图中返回从一个节点到另一个节点的最短路径。我考虑过使用 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;
}