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

Question

我正在上面的图中运行广度优先搜索，以查找从节点0到节点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的列表，试图存储已访问节点的前一个节点，以获取节点列表。参考资料

但它似乎无法正常工作。最短路径是[0,3,2,5,6]。

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

它部分正确但会多出一个1。

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

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

- underdog

---

第二个答案解释了如何在加权图上运行BFS。 - underdog

它说：所有边的权重相同或没有权重。您可以假设所有边的权重相同。 - Ivaylo Stoev

是的，假设所有边都有相同的权值。那么你如何获取节点呢？一个节点x有3个进一步具有相同权重的节点。你会遍历哪一个？你怎么知道哪一个是最好的选择。此外，我的问题与所提供答案完全不同，请再次阅读我的问题。我不是在寻找最短路径（BFS将默认寻找），我想打印最短路径的节点。你明白了吗？ - underdog

打印节点的最佳方法是先到达目标节点，然后打印出到源节点的路径。逻辑与从源节点移动到目标节点相同。 - underdog

通过在访问子节点时保存父节点。假设您从0开始。BFS可能首先访问8、3和1。您将它们的父节点保存为0。然后您访问例如4、2和7。它们的父节点将是8、3和1等等。当您到达目标时，您将迭代父节点返回源。 - Ivaylo Stoev

Answer 1

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

你需要做的是为每个节点存储从起始节点到该节点的路径上的前一个节点。

因此，创建一个名为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);
}

- Anton

---

如果图不是一棵树（有环），则此方法可能无法正常工作。 - c0der

@c0der 图可能包含循环，但最短路径不会。我们通过将每个处理过的节点存储在“visitedNodes”中，并仅将未访问的节点放入队列来确保不会访问任何节点两次。 - Anton

Answer 2

正如您在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<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;
}

这同样适用于循环图，其中一个节点可以有多个父节点。

- c0der

Answer 3

除了用户3290797已经给出的答案之外。

看起来你正在处理一个无权图。我们将其解释为每条边的权重为1。在这种情况下，一旦你将与图的每个节点（广度优先遍历）相关联的根节点的距离，就可以轻松地从任何节点重构最短路径，甚至检测是否存在多个路径。

你需要做的就是对相同的图进行广度（如果您想要每个最短路径）或深度优先遍历，从目标节点开始，并仅考虑深度值恰好比当前节点小1的邻居。 因此，我们需要从距离4（节点6）跳到3、2、1、0，而且只有一种方式（在这种情况下）可以这样做。

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

顺便提一下，这种方法可以很容易地修改为适用于带权图（具有非负权重）：有效的邻居是距离等于当前减去边的权重的那些——这涉及一些实际计算，并直接存储最短路径上的前一个节点可能更好。

- Tymur Gubayev

---

对于带权图，这种方法效果不太好，因为在某些情况下，如果新路径更短，您将不得不访问已标记的顶点。 - vladich

不，唯一的区别在于考虑哪些相邻节点是好的（加权只是更一般的情况）。对于当前节点 N 和从根节点到当前节点的距离为 d(R, N)，如果一个节点 M 在从 R 到 N 的某条最短路径上，则满足条件 d(R, N) = d(R, M) + d(M, N)。 - Tymur Gubayev