Search for shortest path nodes with first width search

Question

I am doing my first search on the above chart 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 the nodes through which BFS works. passed to achieve node 6, for example [0,3,2,5,6] . To do this, I created a list called shortestPath and tried to save the previous nodes of the visited nodes to get a list of nodes. abstract

But that does not work. The shortest path: [0,3,2,5,6]

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

It partially corrects, but gives an additional 1 .

If I start again with the first element 0 the shortestPath list and start moving and returning. For example, 1 does not have an edge to 3 , so I go back and move from 0 to 3 to 5 , I get an answer, but I'm not sure if this is the right way.

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

Answer 1

Saving all the visited nodes in one list does not help to find the shortest path, because at the end you do not know which nodes were the ones that led to the target node and which were dead ends.

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

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

 shortestPath.add(nextNode); 

do the following:

 parentNodes.put(unvisitedNode, nextNode); 

When you reach the goal of the node, you can cross this map to find the path to the source node:

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

Answer 2

In addition to the answer already provided by user 3290797.

It looks like you're dealing with an unweighted schedule. We interpret this because each edge has a weight of 1. In this case, if you connect the distance to the root of a node with each node of the graph (width traversal), it becomes trivial to restore the shortest path from any node and even determine if there are several.

All you need to do is width (in case you want to get the shortest path) or a depth tour of the same graph, starting from the target node and only considering that the neighbors have a depth value exactly 1 less.

So, we need to jump from distance 4 (node ​​6) to 3, 2, 1, 0, and there is only one way (in this case) to do this.

In case we are interested in the shortest path to node 4, the result will be distances 2-1-0 or nodes 4-3-0 or 4-8-0.

BTW, this approach can be easily changed to work with weighted graphs (with non-negative weights) too: the real neighbors are those whose distance is equal to the current minus the edge weight - this includes some actual calculations and direct storage of the previous nodes along the shortest path to be better.

Answer 3

As you can see in acheron55's answer :

"It has an extremely useful property: if all the edges in the graph have no weight (or the same weight), then the first time you visit a node, this is the shortest path to this node from the original node"

So all you have to do is keep track of the path that your goal has been reached. An easy way to do this is to click Queue all the way used to reach the node, not the node itself.
The advantage of this is that when the goal is achieved, the queue holds the path used to achieve it.
Here is a simple implementation:

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

This also applies to circular graphs, where a node can have more than one parent.