Is Dijkstra’s algorithm really the best we can do? We have a nice lower-bound proof for sorting methods – it’s so cool and classic that it gets taught in every algorithms course and excites the students. Later they find out that it’s the only high-quality lower bound proof out there.
We should be able to figure this out by now, dammit. Using fibonacci heaps, which totally suck to program but can be understood as lazy binomial heaps, we can get a runtime of O(V * lg V + E). Well, how big a state space are we exploring? If you look at Dijkstra’s algorithm, you’ll see that it is really just A* search with a heuristic that is provably correct. So we’re already performing a search on the domain. If we’re searching, then it seems like at some level we’re doing a binary search. If we’re doing a binary search, then we know that the minimum time for the algorithm is O(lg(size of the state space)). So how many possible paths are there in a graph? Anyone? Bueller?
