使用广度优先搜索查找最短路径节点

我正在上面的图表上运行广度优先搜索，以找到从Node 0到Node 6的最短路径。

我的代码

 public List shortestPathBFS(int startNode, int nodeToBeFound){ boolean shortestPathFound = false; Queue queue = new LinkedList(); Set visitedNodes = new HashSet(); List shortestPath = new ArrayList(); queue.add(startNode); shortestPath.add(startNode); while (!queue.isEmpty()) { int nextNode = queue.peek(); shortestPathFound = (nextNode == nodeToBeFound) ? true : false; if(shortestPathFound)break; visitedNodes.add(nextNode); System.out.println(queue); Integer unvisitedNode = this.getUnvisitedNode(nextNode, visitedNodes); if (unvisitedNode != null) { queue.add(unvisitedNode); visitedNodes.add(unvisitedNode); shortestPath.add(nextNode); //Adding the previous node of the visited node shortestPathFound = (unvisitedNode == nodeToBeFound) ? true : false; if(shortestPathFound)break; } else { queue.poll(); } } return shortestPath; } 

我需要追踪BFS算法的节点。 遍历到达节点6，如[0,3,2,5,6] 。 为此，我创建了一个名为shortestPath的List并尝试存储受访节点的先前节点，以获取节点列表。 简称

但它似乎没有用。 最短路径为[0,3,2,5,6]

在列表中我得到的是Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]

它部分正确，但额外1 。

如果我再次从shortestPath列表的第一个元素0开始并开始遍历和回溯。 像1没有3的边缘，所以我回溯并从0移动到3到5 ，我会得到答案但不确定这是否是正确的方法。

获取最短路径节点的理想方法是什么？

Answer 1

将所有访问的节点存储在单个列表中对于找到最短路径没有帮助，因为最终您无法知道哪些节点是导致目标节点的节点，哪些节点是死角。

您需要做的是每个节点将前一个节点存储在起始节点的路径中。

因此，创建一个Map parentNodes ，而不是：

 shortestPath.add(nextNode); 

做这个：

 parentNodes.put(unvisitedNode, nextNode); 

到达目标节点后，您可以遍历该映射以查找返回到起始节点的路径：

 if(shortestPathFound) { List shortestPath = new ArrayList<>(); Integer node = nodeToBeFound; while(node != null) { shortestPath.add(node) node = parentNodes.get(node); } Collections.reverse(shortestPath); } 

Answer 2

除了user3290797已经给出的答案。

看起来你正在处理一个未加权的图形。 我们解释这一点，因为每条边的权重都为1.在这种情况下，一旦你将根节点的距离与图的每个节点（广度优先遍历）相关联，重建最短路径就变得微不足道了。节点，甚至检测是否有多个节点。

您需要做的就是宽度 – （如果您想要每条最短路径）或从目标节点开始的同一图形的深度优先遍历，并且仅考虑深度值恰好小于1的邻居。

所以我们需要从距离4（节点6）跳到3,2,1,0，并且只有一种方法（在这种情况下）这样做。

如果我们对节点4的最短路径感兴趣，结果将是距离2-1-0或节点4-3-0或4-8-0。

顺便说一句，这种方法很容易被修改为与加权图（非负权重）一起使用：有效邻居是距离等于当前减去边缘权重的邻居 – 这涉及一些实际计算并直接存储先前的节点最短路径可能会更好。

Answer 3

正如你在acheron55中看到的那样 ：

“它具有非常有用的特性，如果图中的所有边都未加权（或相同的权重），那么第一次访问节点是从源节点到该节点的最短路径”

所以你要做的就是跟踪目标已到达的路径。 一种简单的方法是将Queue用于到达节点的整个路径，而不是节点本身。
这样做的好处是，当达到目标时，队列将保持用于到达目标的路径。
这是一个简单的实现：

 /** * unlike common bfs implementation queue does not hold a nodes, but rather collections * of nodes. each collection represents the path through which a certain node has * been reached, the node being the last element in that collection */ private Queue> queue; //a collection of visited nodes private Set visited; public boolean bfs(Node node) { if(node == null){ return false; } queue = new LinkedList<>(); //initialize queue visited = new HashSet<>(); //initialize visited log //a collection to hold the path through which a node has been reached //the node it self is the last element in that collection List pathToNode = new ArrayList<>(); pathToNode.add(node); queue.add(pathToNode); while (! queue.isEmpty()) { pathToNode = queue.poll(); //get node (last element) from queue node = pathToNode.get(pathToNode.size()-1); if(isSolved(node)) { //print path System.out.println(pathToNode); return true; } //loop over neighbors for(Node nextNode : getNeighbors(node)){ if(! isVisited(nextNode)) { //create a new collection representing the path to nextNode List pathToNextNode = new ArrayList<>(pathToNode); pathToNextNode.add(nextNode); queue.add(pathToNextNode); //add collection to the queue } } } return false; } private List getNeighbors(Node node) {/* TODO implement*/ return null;} private boolean isSolved(Node node) {/* TODO implement*/ return false;} private boolean isVisited(Node node) { if(visited.contains(node)) { return true;} visited.add(node); return false; } 

这也适用于循环图，其中节点可以具有多个父节点。