Written by Chris Piech.
Nov 30th, 2016
A common pattern amongst the search algorithms (with the semi-exception of recursive exploration) is that they all build a collection which stores paths (or in some implementations nodes) that should be explored. I call this the search "todo" list.
Here is search pseudocode. Dijkstra uses a PriorityQueue to store the todo list. Change the collection type to switch between Deapth First Search, Breadth First Search and A Star.
The fundamental difference between Depth First Search, Breadth First Search, Dijkstra and A Star is the collection used to represent the "todo" list of paths to process.
Algorithm | Todo Collection | Benefit |
---|---|---|
Depth First Search | Stack | Uses little memory |
Breadth First Search | Queue | Finds shortest hops |
Dijkstra's Algorithm | Priority Queue | Finds shortest path |
A Star | Priority Queue | Finds shortest path fast |
In all cases Recursive Exploration is the same of Depth First Search.
Breadth first search always finds the shortest path for unweighted graphs, but not for weighted graphs.
For graphs with unweighted edges, Breadth First Search is the same as Dijkstra's.