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

问题描述

我在上图中运行广度优先搜索，以找到<$ c $的最短路径c>节点0 到节点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 的列表&尝试存储受访节点的先前节点，以获取节点列表。 Referred

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]

在列表中我得到的是最短路径：[0,0,0,0,1,3,3,2,5]

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

It's partially correct but gives the extra 1 .

如果我再次从第一个元素 $ <$ code> shortestPath 列表&开始遍历&回溯。像 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.

因此，创建一个地图 Map< Integer，Integer> parentNodes ，而不是：

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屋！