用广度优先搜索寻找最短路径节点 [英] Finding the shortest path nodes with breadth first search

问题描述

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

I am running breadth first search on the above graph to find the shortest path from Node 0 to 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 的列表 &尝试存储访问节点的先前节点，以获取节点列表.引用

I need to track down the nodes through which the BFS algo. traversed to reach node 6, like [0,3,2,5,6]. For that I have created a List named shortestPath & trying to store the previous nodes of the visited nodes, to get the list of nodes. Referred

但它似乎不起作用.最短路径是[0,3,2,5,6]

But it doesn't seem to work. The shortest path is [0,3,2,5,6]

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

部分正确，但提供了额外的 1 .

It's partially correct but gives the extra 1 .

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

If I again start from the first element 0 of the shortestPath list & start traversing & backtracking. Like 1 doesn't has an edge to 3, so I backtrack & move from 0 to 3 to 5, I will get the answer but not sure if that's the correct way.

获得最短路径节点的理想方法是什么?

What is the ideal way to getting the nodes for the shortest path?

推荐答案

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

Storing all the visited nodes in a single list is not helpful for finding the shortest path because in the end you have no way of knowing which nodes were the ones that led to the target node, and which ones were dead ends.

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

What you need to do is for every node to store the previous node in the path from the starting node.

所以，创建一个地图 MapparentNodes，而不是这个:

So, create a map Map<Integer, Integer> parentNodes, and instead of this:

shortestPath.add(nextNode);

这样做:

parentNodes.put(unvisitedNode, nextNode);

到达目标节点后，您可以遍历该地图以找到返回起始节点的路径:

After you reach the target node, you can traverse that map to find the path back to the starting node:

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

这篇关于用广度优先搜索寻找最短路径节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！