As part of my work at Triplebyte, I spend some time explaining algorithms to people. On some topics, my explanations are quite different to the explanations that students normally see. Here is my attempt to tersely sketch my explanation of the differences between graph search algorithms.
When you do a graph search, you basically do it by maintaining some set of nodes that you need to explore at some point. Graph search looks something like this:
def search(graph, start_node):
explored = set()
frontier = set()
while frontier:
node = frontier.pop()
# skip this node if we've already explored it
if node in explored:
next
explored.add(node)
for neighbor in graph.neighbors(node):
if neighbor not in explored:
frontier.add(node)
return explored
That algorithm returns a set of nodes which it could reach from start_node.
In the node = frontier.pop() line, which node should we pop from the frontier?
We could have frontier be a stack, which uses a last-in-first-out rule. If we do that, our graph search is a depth-first search.
Alternatively, we could have frontier be a queue. Queues give you elements in a first-in-first-out order. Assuming our graph is unweighted, this means that you’re always going to explore nodes closest to the start node before nodes farther away. So if you are keeping track of the path, you’re guaranteed to find the shortest path from start_node to every other node.
So BFS will get you the shortest path from one node to another on an unweighted graph, while DFS makes no such guarantee. BFS gets you shortest paths because it explores the nodes in ascending order of distance from the start node.
Resources on this:
Generalizing to weighted graphs
Why does BFS always get shortest paths? Because it explores nodes in order of their distance from the start node, and once it’s explored a node it never explores it again. So each node will only be explored via its shortest path.
So the key is the FIFO structure of the queue–because the graph is unweighted, if you explore nodes in the order in which you first encounter them, you’re finding the shortest paths.
But that doesn’t work for weighted graphs, because FIFO queues don’t take into account the edge costs. We still want to explore nodes in ascending order of distance from the start node. How can we do this?
Easy! Instead of a FIFO queue, we can use a priority queue, where the priority of each node in the queue is its distance from the start node.
This is known as Dijkstra’s algorithm. It’s just BFS generalized to weighted graphs by using a priority queue instead of a FIFO queue.
Limitations of Dijkstra’s algorithm
Dijkstra’s algorithm finds shortest paths because it explores all the nodes in ascending order of their distance from the start node.
If your graph has negative edge weights in it, Dijkstra’s algorithm will not correctly explore the graph in ascending order of distance. This means that it might not return shortest paths.
So Dijkstra’s algorithm only finds shortest paths on graphs with positive edge weights.
Other notes
You can implement a queue with two stacks. Your explored set should be implemented as a hash set, to minimize lookup times. You can implement a priority queue with a binary heap.
My graph search implementation above involves adding the same node to frontier multiple times. In the case of BFS and DFS, this is unhelpful and you should consider adding an auxilliary hash set which stores the contents of frontier and allows you to quickly check whether nodes are in it and then avoid adding them to the frontier set if they’re already in there. However, in the case of Dijkstra’s algorithm, we might find a shorter path to a node after the node has already been added to the priority queue. In my code above, this case is handled by the logic to skip exploring a node if it’s already been explored. So it’s only going to actually be explored with its lowest priority. If you want to be super fancy, you can instead do this by using a priority queue which quickly allows you to decrease the priority of one of its elements. You can implement a queue which efficiently supports this decreaseKey operation with a Fibonacci heap, which lets you do decreaseKey in amortized \(O(1)\) time. However Fibonacci heaps are massively complicated and have a big constant factor (due to the fact that you can’t represent them in an array like binary heaps), so you probably shouldn’t actually do this.
DFS usually takes less memory than BFS. Explanation here. So if you need to completely explore a graph, DFS is better.
If you need to explore a graph roughly in order but don’t want to pay the memory cost of BFS, you can use iterative deepening depth-first search.
A* is a modification of Dijsktra’s algorithm which uses a heuristic added to the distance from the start node as the priority in the priority queue. If this heuristic always underestimates the distance from the node to the end node, A* will give you correct results. A* needs to have an optimistic heuristic for the same reason that Dijkstra’s algorithm fails on graphs with negative edge weights.
If you want to find shortest paths on a graph with negative edge weights, you can use the Floyd-Warshall algorithm, which is much slower than the graph search algorithms I’ve been describing, because it can’t only look at nodes once and then be confident that it has found the shortest path to them.
Questions to test your understanding
Does Dijkstra’s algorithm find shortest paths on a graph if some of its edges have weight 0? show answer
Does BFS find shortest paths on a graph which is weighted, but all its edge weights are the same positive number? show answer
If you want to find the shortest path from point A to point B on an unweighted graph, should you use BFS or DFS? show answer
Suppose I’m implementing a garbage collection algorithm, which is designed to find all the objects in memory which are still reachable, and then delete all the other elements. I want to do this by a graph search starting from the objects pointed to by local variables. Should I use BFS or DFS? show answer