Graphs: Search algorithm comparison

The common graph search algorithms all have a common structure:

1. We can walk walk the graph but don't have random access i.e. we can only ever discover nodes connected to the set of nodes that we have found so far.
2. As we reach nodes we remember them.
3. As we reach nodes we queue them up for future exploration.
4. As we reach nodes we remember some details about the shortest path there e.g. length, or predecessor.

The choice of how we queue up nodes for future exploration is the main difference between the search algorithms:

• Depth first search: stack, LIFO
  • Finds a path to goal
• Breadth first search: queue, FIFO
  • Finds shortest path to goal (unweighted edges)
• Dijkstra: Priority queue by minimal cost from start
  • Finds shortest path to goal (weighted edges)
• A*: Priority queue by minimal estimated from start to goal
  • Efficiently finds shortest path to goal (weighted edges)

The choice of what to remember in #4 is problem specific and doesn't relate to the algorithm.