BFS
Simple BFS can be used to find shortest distance from a source point if the graph /implicit graph is unit length. The level is the shortest path. Record the size and do another inner for loop can make sure we do the level counting right.
If the edge weight is not unit length, we can do it with Dijkstra Shortest Path algorithm.
int level=0;
while(!q.isEmpty()) {
int qSize = q.size();
for(int k=0; k<qSize; k++) {
...
}
level++;
}
Some problems are of implicit BFS, the level by level out-reach shortest path/ minimum number of steps/ ...
ShortestPath calculation starting from destination
If we are finding the shortest path from source to nearest destination, we can also do it reversely, calculate the path length from all possible destinations to the sources and do the Math.min when reached source.
We might desire such computation when the number of possible destinations is much fewer than number of sources.
317. Shortest Distance from All Buildings
If we just care about the shortest path, we can first collect all destinations, and do BFS from the the destinations, the closest destination will reach the source first. For example below, the closest gate (0) will reach the room (INF) first.
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
Dijkstra Algorithm
If the weight of the edge is not uniform/unit, we implement the Dijkstra algorithm within the BFS and find the solution.
Some problem requires us to handle multiple shortest paths scenario. We just need to additionally handle when path[v] + edge(v, u) = path[u]
Using Dijkstra algorithm: single source all pairs shortest path
class Solution {
class Point{
int x, y, length;
public Point(int x, int y, int length) {
this.x = x; this.y = y; this.length = length;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m = maze.length, n = maze[0].length;
PriorityQueue<Point> q = new PriorityQueue<>((a, b)->a.length - b.length);
int path[][] = new int[m][n];
String[][] pathStr = new String[m][n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
path[i][j] = Integer.MAX_VALUE;
pathStr[i][j] = "";
}
}
final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1,0}};
final char[] dirChar = {'r', 'd', 'l', 'u'};
boolean[][] visited = new boolean[m][n];
path[ball[0]][ball[1]] = 0; //start with source d = 0
q.offer(new Point(ball[0], ball[1], 0));
while(!q.isEmpty()) {
Point v = q.poll();
if(v.x==hole[0] && v.y==hole[1]) return pathStr[v.x][v.y]; //early termination if the destination is processed
visited[v.x][v.y] = true;
for(int k=0; k<4; k++) {
int row = v.x, col = v.y, length=0;
while(row + dir[k][0]>=0 && row + dir[k][0]<m && col + dir[k][1]>=0 && col + dir[k][1]<n &&
maze[row+dir[k][0]][col+dir[k][1]]==0 ) {
row = row + dir[k][0]; col = col + dir[k][1];
length++;
if(row == hole[0] && col == hole[1]) break;
}
//already in processed set if visited,
//below process has no effect on its shortest path according to Dijkstra algorithm
if(!visited[row][col]) {
if(path[v.x][v.y] + length < path[row][col]) {
path[row][col] = path[v.x][v.y] + length;
pathStr[row][col] = pathStr[v.x][v.y] + dirChar[k];
q.offer(new Point(row, col, path[v.x][v.y] + length));
} else if(path[v.x][v.y] + length == path[row][col]) {
if(pathStr[row][col].compareTo(pathStr[v.x][v.y] + dirChar[k])>0)
pathStr[row][col] = pathStr[v.x][v.y] + dirChar[k];
}
}
}
}
return path[hole[0]][hole[1]] == Integer.MAX_VALUE? "impossible": pathStr[hole[0]][hole[1]];
}
}
But for point-to-point shortest path, we don't really need Dijkstra algorithm, just simple BFS will work. It will be faster because PriorityQueue takes nlogn time, which is slower than LinkedList.
class Solution {
class Point{
int x, y;
public Point(int x, int y) {
this.x = x; this.y = y;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m = maze.length, n = maze[0].length;
Queue<Point> q = new LinkedList<>();
int path[][] = new int[m][n];
String[][] pathStr = new String[m][n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
path[i][j] = Integer.MAX_VALUE;
pathStr[i][j] = "";
}
}
final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1,0}};
final char[] dirChar = {'r', 'd', 'l', 'u'};
path[ball[0]][ball[1]] = 0;
q.offer(new Point(ball[0], ball[1]));
while(!q.isEmpty()) {
Point v = q.poll();
//4 possible directions
for(int k=0; k<4; k++) {
int row = v.x, col = v.y, length=0;
while(row + dir[k][0]>=0 && row + dir[k][0]<m && col + dir[k][1]>=0 && col + dir[k][1]<n &&
maze[row+dir[k][0]][col+dir[k][1]]==0 ) {
row = row + dir[k][0]; col = col + dir[k][1];
length++;
if(row == hole[0] && col == hole[1]) break;
}
if(row == v.x && col == v.y) continue; //this dir not possible.
if(path[v.x][v.y] + length <= path[row][col]) {
if(path[v.x][v.y] + length == path[row][col]) {
if(pathStr[row][col].compareTo(pathStr[v.x][v.y] + dirChar[k])>0)
pathStr[row][col] = pathStr[v.x][v.y] + dirChar[k];
} else {
path[row][col] = path[v.x][v.y] + length;
pathStr[row][col] = pathStr[v.x][v.y] + dirChar[k];
}
q.offer(new Point(row, col));
}
}
}
return path[hole[0]][hole[1]] == Integer.MAX_VALUE? "impossible": pathStr[hole[0]][hole[1]];
}
}
Two Parallel Queues for BFS
Sometimes, other than putting the TreeNode into Queue for BFS, we might need to track additional information along the way. We can use a self-defined pair / two parallel queues to achieve this.
314. Binary Tree Vertical Order Traversal
TreeMap<Integer, List<Integer>> colListMap = new TreeMap<>();
Queue<TreeNode> nodeQ = new LinkedList<>();
Queue<Integer> colIndexQ = new LinkedList<>();
nodeQ.add(root); colIndexQ.add(0);
while(!nodeQ.isEmpty()) {
TreeNode node = nodeQ.poll();
int col = colIndexQ.poll();
if(node!=null) {
if(!colListMap.containsKey(col))
colListMap.put(col, new ArrayList<Integer>());
colListMap.get(col).add(node.val);
nodeQ.offer(node.left); colIndexQ.offer(col-1);
nodeQ.offer(node.right); colIndexQ.offer(col+1);
}
}
Expand Out vs Converge /Diffuse inwards BFS
We are familar with the normal BFS that starts from a point/ a root node in tree. The other style is like the leaves bite approach in BFS topological sort. We start from the outside and move inwards, this will give the shortest path from the outside to the points along the way.
Some problem can be solved easier with this approach.