Something I've wondered for a while: how many things actually use Dijkstra's algorithm, in practice? I know how it works, and I've implemented shortest-path gra

Something I've wondered for a while: how many things actually use Dijkstra's algorithm, in practice? I know how it works, and I've implemented shortest-path graph algorithms a few times, but it's always been fairly easy to find at least some kind of admissable heuristic, so why would you implement Dijkstra over A-star? (edit: stupid hacker news markup wont let me escape the asterisk) Obviously, when your graph has some sort of geometric interpretation (i.e. a map or something), euclidian distance is the obvious choice (or Manhattan distance if you're on a grid, etc.), but even for relatively abstract things you might use graph search for you can usually figure out something. Like, if you're trying to find the shortest solution to a sliding block puzzle using a graph algorithm (where each node connects to all other nodes you can get to in one move), you can use some sort heuristic based on the number of inversions, or whatever. Even if your heuristic is kinda bad, it's almost certainly better than no heuristic at all. Dijkstra's algorithm has always seemed to me to be the "canonical academic shortest-path algorithm that always works", but in reality everyone uses A-star instead, because for all practical purposes it's way better, and not much more complicated to implement.