使用广度优先搜索查找最短路径节点-Java 学习之路

enter image description here

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

我的代码

public List<Integer> shortestPathBFS(int startNode, int nodeToBeFound){
        boolean shortestPathFound = false;
        Queue<Integer> queue = new LinkedList<Integer>();
        Set<Integer> visitedNodes = new HashSet<Integer>();
        List<Integer> shortestPath = new ArrayList<Integer>();
        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，并尝试存储受访节点的先前节点，以获取节点列表 . Referred

但它似乎没有用 . 最短的路径是 [0,3,2,5,6]

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

它部分正确，但给出了额外的 1 .

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

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

3 回答

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

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

所以，创建一个 Map Map<Integer, Integer> parentNodes ，而不是这个：
```
shortestPath.add(nextNode);
```
做这个：
```
parentNodes.put(unvisitedNode, nextNode);
```
到达目标节点后，您可以遍历该映射以查找返回到起始节点的路径：
```
if(shortestPathFound) {
    List<Integer> shortestPath = new ArrayList<>();
    Integer node = nodeToBeFound;
    while(node != null) {
        shortestPath.add(node)
        node = parentNodes.get(node);
    }
    Collections.reverse(shortestPath);
}
```
回复于 2024-04-29T12:16:20+08:00
0

除了user3290797已经给出的答案 .

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

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

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

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

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

回复于 2024-04-29T12:16:20+08:00

正如您在acheron55 answer中看到的：

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

所以你要做的就是跟踪到达目标的路径 . 一种简单的方法是将用于到达节点的整个路径推入 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<List<Node>> queue;

//a collection of visited nodes
private Set<Node> 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<Node> 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<Node> pathToNextNode = new ArrayList<>(pathToNode);
                pathToNextNode.add(nextNode);
                queue.add(pathToNextNode); //add collection to the queue
            }
        }
    }

    return false;
}

private List<Node> 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;
}

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

回复于 2024-04-29T12:16:20+08:00

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

3 回答

相关问题