A star
- How do we get our estimate?
- Estimate is an arbitrary heuristic h(v, goal).
- heuristic: “using experience to learn and improve”
- Doesn’t have to be perfect!
Note, if edge weights are all equal (as here), Dijkstra’s algorithm is just Breadth First Search.
This is a good tool for understanding distinction between order in which nodes are visited by the algorithm vs. the order in which they appear on the shortest path.
- Unless you’re really lucky, vastly more nodes are visited than exist on the shortest path.