In what context does this work?
As you probably know, there are two types of graphs in terms of their edges:
Graphs with unweighted edges (the cost of traversing/processing/... each edge is 1)
Graphs with weighted edges (each edge has a particular cost to be traversed/removed/processed/... particular not necessary unique)
There are a couple of classic problems on graphs, but one of the most approached one is to find the shortest path between some node(we call it the source node) and all the other nodes.
You are going to see this problem in a lot of different formats:
Could be shortest path from a set of nodes to some specific node => which is obviously exactly the same
You can have some "obstacles"(or "bad nodes" or "bad cells") => which is exactly the same but you are not going to include those nodes in your graph/algorithm.
You can have some forbidden actions(for example, you are not allowed to move from some node to another if their sum is X) => which is exactly the same but you are not going to include those edges in your graph/algorithm.
What I am saying here is that BFS is a standard algorithm. Solving a problem involving it is just a matter of how you construct the graph on which you will execute BFS.
1. How does it work?
Initially, you insert the source node in a queue. In that queue you will have the nodes for which you have found the shortest path. As long as that queue is not empty, you take the first node in the queue(known as front). Because you know it's shortest path, you will try out each of it's neighbors and if one is not visited yet, bingo! We now know the shortest path for that node too. What do we do now? We set it's shortest path and insert it into the queue.
2. Why does it work?
It seems like we know the shortest path from the source node to some node the very first time we visit that node. Why is this true tho?
Because the edges are unweighted. This leads to those nodes in the queue being "sorted increasingly" by the shortest path length. Let's suppose for a second they are not. How could we even visit some node with shortest path of 5 before a node with shortest path of 3? For getting to the one 5 units far away we have to traverse some node which is 3 units far away.
If the edges are weighted you probably know very well there is some mr. Dijkstra who thought of that before us.
3. How fast does it work?
O(n + m) where n = no. of nodes and m = no. of edges. But why?...
As we have said in the previous paragraph, each time we visit some node for the first time, we know it's shortest path. So each node is going to be processed(that means we set it's shortest path and push it into the queue) exactly once. Now, each edge A-B can be processed at most 2 times. If the first node in the queue is either A or B.
4. What about multiple sources?
We just push all of them into the queue initially. And that's it. It works exactly the same, no matter where that shortest path started from.
5. Some practical examples:
Almost all the problems with matrices in which you have to find "the shortest path to some cell with the condition bla bla bla" Everything similar to the Lee Algorithm. Those matrices are in fact graphs.
You can check 01-Matrix out. I have solved and coded it in this video, but don't you dare to click the link before you have tried to solve it yourself.
Lots of love,
Andy.
