Comment

Comment by apnorton

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue:

Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue)

Dijkstra: Priority is distance so far + next edge distance

A*: Priority is distance so far + next edge distance + estimate of distance to target node.

This also helps me remember whether the estimate must over- or under-estimate: Since Dijkstra is making the estimate "0", clearly the "admissible heuristic" criteria must be an under-estimation.

parent apnorton 1 year ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton