I have a problem in calculating the shortest path through BFS algorithm in Java.
When I tried to define a path from Node 0 to Node 7 , I got this result. (0 -> 2 -> 3 -> 4 -> 5)
How can I fix the issue?
Here is my Node Class
public class Node {
private final int value;
private final Set<Node> siblingNodes;
public Node(int value) {
this.value = value;
siblingNodes = new HashSet<Node>();
}
public Set<Node> getSiblingNodes() {
return siblingNodes;
}
public boolean equals(Node compareTo) {
return (compareTo.getValue() == value);
}
public int getValue() {
return value;
}
public void addSiblingNode(Node node) {
siblingNodes.add(node);
}
}
Here is the code snippets shown below.
public static void main(String[] args) {
/**
*
* 1 -> 5
* 0 -> -> 4
* 2 -> 3 -> 6 -> 7
*
*/
Node node0 = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
node0.addSiblingNode(node1);
node0.addSiblingNode(node2);
Node node3 = new Node(3);
node2.addSiblingNode(node3);
Node node4 = new Node(4);
node3.addSiblingNode(node4);
Node node5 = new Node(5);
Node node6 = new Node(6);
node4.addSiblingNode(node5);
node4.addSiblingNode(node6);
Node node7 = new Node(7);
node6.addSiblingNode(node7);
List<Node> shortestPath = getDirections(node0, node7);
for(Node node : shortestPath) {
System.out.println(node.getValue());
}
}
public static List<Node> getDirections(Node sourceNode, Node destinationNode) {
// Initialization.
Map<Node, Node> nextNodeMap = new HashMap<Node, Node>();
Node currentNode = sourceNode;
Node previousNode = sourceNode;
// Queue
Queue<Node> queue = new LinkedList<Node>();
queue.add(currentNode);
/*
* The set of visited nodes doesn't have to be a Map, and, since order
* is not important, an ordered collection is not needed. HashSet is
* fast for add and lookup, if configured properly.
*/
Set<Node> visitedNodes = new HashSet<Node>();
visitedNodes.add(currentNode);
//Search.
while (!queue.isEmpty()) {
currentNode = queue.remove();
if (currentNode.equals(destinationNode)) {
// Handle case where the node leading to the destinatino node
// itself pointed to multiple nodes. In this case,
// nextNodeMap is incorrect and we need to rely on the previously
// seen node.
// Also need to check for edge-case of start node == end node.
if (!previousNode.equals(currentNode)) {
nextNodeMap.put(previousNode, currentNode);
}
break;
} else {
for (Node nextNode : currentNode.getSiblingNodes()) {
if (!visitedNodes.contains(nextNode)) {
queue.add(nextNode);
visitedNodes.add(nextNode);
// Look up of next node instead of previous.
nextNodeMap.put(currentNode, nextNode);
previousNode = currentNode;
}
}
}
}
// If all nodes are explored and the destination node hasn't been found.
if (!currentNode.equals(destinationNode)) {
throw new RuntimeException("No feasible path.");
}
// Reconstruct path. No need to reverse.
List<Node> directions = new LinkedList<Node>();
for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) {
directions.add(node);
}
return directions;
}
}
CodePudding user response：
It's a good idea to use a Map to construct the path between nodes. But the probless is that you're overriding Values since there couldn't more than one entry with same Key (4 -> 6 has been overridden with 4 -> 5, and you received an incorrect result).
To solve this issue we can reverse the Map, i.e. the Keys would represent sibling-nodes (keys are unique), and Values - parent-nodes (values can be duplicated). And when the destination node was found (or all nodes has been visited) the path would be constructed in restored in reversed order, i.e. from destination to source (we would need to reverse the list).
Also note that a HashSet of visited nodes is redundant since this information is already reflected in the Map.
That how BFS implementation might look like:
public static List<Node> getDirections(Node source, Node destination) {
Map<Node, Node> paths = new HashMap<>(); // Map of paths also allows to track the visited nodes
Queue<Node> queue = new ArrayDeque<>(); // is more performant than LinkedList
queue.add(source);
paths.put(source, null); // the starting point of the path
boolean isFound = false;
while (!isFound && !queue.isEmpty()) {
Node current = queue.remove();
for (Node sibling : current.getSiblingNodes()) {
if (paths.containsKey(sibling)) continue;
// update the Map of paths
paths.put(sibling, current);
// the target node was found
if (sibling.equals(destination)) {
isFound = true; // we need to terminate the search, no need to explore all nodes if the path is found
break;
}
queue.add(sibling); // adding the sibling to the queue
}
}
return getPath(source, destination, paths);
}
Helper method for generating the path:
public static List<Node> getPath(Node start, Node end, Map<Node, Node> paths) {
List<Node> path = new ArrayList<>();
Node current = end;
path.add(current);
while (current != start && current != null) { // if there's no path from start to end current eventually will become null
path.add(paths.get(current));
current = paths.get(current);
}
Collections.reverse(path);
return current != null ? path : Collections.emptyList();
}
Note equals() implementation in the Node class actually doesn't override java.lang.Object.equals() because the signature doesn't match. Also, implementation of hashCode() is missing, which goes against the contract of the equals(). Therefore, in hash-based collections, default implementations for both equals and hashCode would be used. It didn't cause troubles in the original code, only because OP was using literally the same objects.
Here's an example of correct implementation:
public class Node {
private final int value;
private final Set<Node> siblingNodes = new HashSet<>();
// constructor, getters, addSiblingNode(), etc.
@Override
public boolean equals(Object o) {
return o instanceof Node other && value == other.value;
}
@Override
public int hashCode() {
return Objects.hash(value);
}
}
main()
public static void main(String[] args) {
// sample data from the question
List<Node> shortestPath = getDirections(node0, node7);
String path = shortestPath.stream()
.map(Node::getValue)
.map(String::valueOf)
.collect(Collectors.joining(" -> "));
System.out.println(path);
}
Output:
0 -> 2 -> 3 -> 4 -> 6 -> 7
CodePudding user response：
Your getDirections() implementation seems correct. But there is a problem with the Node class. You should add the following two methods to Node.
These are needed to store Node objects in a Map or Set.
@Override
public int hashCode() {
return value;
}
@Override
public boolean equals(Object obj) {
return obj instanceof Node n
&& n.value == value;
}
output:
0
2
3
4
6
7