java - Finding the shortest path nodes with breadth first search

Question

I am running breadth first search on the above graph to find the shortest path from Node 0 to Node 6.

My code

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;
    }

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

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

In the list what I get is Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]

It's partially correct but gives the extra 1 .

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?

Answer 1

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.

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

shortestPath.add(nextNode);

do this:

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);
}