I am pasting my code for:
Given an undirected and unweighted graph, prints all shortest paths from a src node to a dest node. In the example I use, the src node is a and dest node is f
I am representing the undirected graph via a HashMap
I have 2 very specific questions about my code. I am trying to trace it on paper to find the answer but not able to find an example to fully answer my query.
import java.util.*;
class ShortestPathsAll {
static Map<Character, List<Character>> graph = new HashMap<>();
public static void main(String[] args) {
graph.put('a',List.of('c','b'));
graph.put('b',List.of('a','f'));
//graph.put('c',List.of('a','d'));
graph.put('c',List.of('a','d','f'));
graph.put('d',List.of('c','e'));
graph.put('e',List.of('d','f'));
//graph.put('f',List.of('b','e'));
graph.put('f',List.of('b','e','c'));
var src = 'a';
var dest = 'f';
var currPath = new ArrayList<>(List.of(dest));
var parents = allShortestPaths(graph);
List<List<Character>> paths = new ArrayList<>();
printPaths(parents, paths,currPath,src,dest);
System.out.println(paths);
}
static Map<Character, List<Character>> allShortestPaths(Map<Character, List<Character>> graph) {
Map<Character, Integer> distance = new HashMap<>();
Map<Character, List<Character>> parents = new HashMap<>();
Queue<Character> q = new LinkedList<>();
Set<Character> visisted = new HashSet<>();
var src = 'a'; var dest = 'f';
for(var key:graph.keySet()) {
distance.put(key,Integer.MAX_VALUE);
parents.put(key, new ArrayList<>());
}
q.offer(src);
distance.put(src,0);
while(!q.isEmpty()) {
var node = q.poll();
if (visisted.contains(node)) {
continue;
}
visisted.add(node);
List<Character> children = graph.get(node);
for(var child:children) {
if(visisted.contains(child)) {
continue;
}
if(distance.get(child)>distance.get(node)+1) {
if(distance.get(child)!=Integer.MAX_VALUE) {
System.out.println("found it again");
}
distance.put(child, distance.get(node)+1);
parents.get(child).clear();
parents.get(child).add(node);
} else {
parents.get(child).add(node);
}
q.offer(child);
}
}
System.out.println(distance);
System.out.println(parents);
return parents;
}
static void printPaths(Map<Character, List<Character>> parents,
List<List<Character>> paths, List<Character> currPath, Character src, Character dest) {
if(currPath.get(currPath.size()-1) == src) {
paths.add(new ArrayList<>(currPath));
return;
}
for(var parent:parents.get(dest)) {
if (parent == null) {
return;
}
currPath.add(parent);
printPaths(parents, paths, currPath, src, parent);
currPath.remove(currPath.size()-1);
}
}
}
Inside the for-loop in the function allShortestPaths, I have an if-else block as follows:
if(distance.get(child)>distance.get(node)+1) {
if(distance.get(child)!=Integer.MAX_VALUE) {
System.out.println("found it");
}
distance.put(child, distance.get(node)+1);
parents.get(child).clear();
parents.get(child).add(node);
} else {
parents.get(child).add(node);
}
Given my understanding of BFS, I am unable to on paper come up with a graph which will make me see this print statement at all System.out.println("found it again"); I think the reason is that in my current implementation, a node may enter the queue more than once but once a shortest path is seen, and the way I mark visited, the same node can never be visited from a longer path? Basically, in short, I am trying to trace and find a case where the print can show up.
This one is more serious and I am not 100% clear on this. The if-else block has an else part:
else {
parents.get(child).add(node);
}
Blindly says that add the node to the list rather than
else if(distance.get(child) == distance.get(node)+1)
Without the else-if, is it possible that I may have a smaller distance stored and it might get over-written with a larger distance? Again, I think that since I do the visited check at the start of for-loop this might never happen. Is it true?
I am unable to on paper come up with a graph which will make me see this print statement at all
System.out.println("found it again");... the way I mark visited, the same node can never be visited from a longer path?
Your analysis is correct. It can never happen. Maybe you got that code from an implementation intended for a weighted graph? In that case it is possible to have a plain BFS (with a plain queue) revisit a node via a shorter path...
The
if-elseblock has anelsepart: .. Without theelse-if, is it possible that I may have a smaller distance stored and it might get over-written with a larger distance? Again, I think that since I do the visited check at the start of for-loop this might never happen. Is it true?
First of all, no distance gets overwritten in that else block, so that is not something to worry about. Only parents.get(child).add(node); gets executed there.
Two things can be true in that else block:
distance.get(child)==distance.get(node)+1. In that case it is right to perform parents.get(child).add(node);, since we have found an equally short path that is an alternative to the one already found before.
distance.get(child)==distance.get(node) (one less). This happens when we have two nodes that are at the same distance, and both are on the current BFS "frontier", but the child one happens to be still in the queue, so it was no yet visited. In that case we have this equality, and it would be wrong to perform parents.get(child).add(node); because the current path to that child is not the shortest.
Here is a simple graph that reproduces the problem:
a (start)
┌─┴─┐
▼ ▼
b──►c──►f (target)
The queue will first have {a}, then {b, c}. When b is popped, and we check its neighbor c, we get in the problematic situation. If in your code we initialise like this:
graph.put('a',List.of('b','c'));
graph.put('b',List.of('c'));
graph.put('c',List.of('f'));
graph.put('f',List.of());
The output ends with:
[[f, c, a], [f, c, b, a]]
...and obviously includes a path that is not the shortest!
If we correct the code and have:
} else if (distance.get(child)==distance.get(node)+1) {
...then the output will have:
[[f, c, a]]
So you need the else if version.