What is the best single-source shortest path algorithm for programming contests?

Question

I was working on this graph problem from the UVa problem set. It's a single-source-shortest-paths problem with no negative edge weights. From what I've gathered, the algorithm with the best big-O running time for such problems is Dijkstra with a Fibonacci heap as the priority queue, although practically speaking a binary heap is easier to implement and works pretty well too.

However, it would seem that even a binary heap takes quite some time to roll, and in a competition time is limited. I am aware that the STL provides some heap algorithms and priority queues, but they don't seem to provide a decrease-key function which Dijkstra's needs. Or am I wrong here?

It seems that another possibility is to simply not use Dijkstra's. This forum thread has people claiming that they solved the above problem with breadth-first search / Bellman-Ford, which are much easier to code up. (Edit: OTOH, Dijkstra's with an unsorted array for the priority queue timed out.) That BFS/Bellman-Ford worked surprised me a little as I thought that the input size was quite large. I guess different problems will require solutions of different complexity, but my question is, how often would I need to use Dijkstra's in such competitions? Should I practice more on the simpler-but-slower algorithms instead?

Answer 1

The Boost Graph Library appears to have implementations for both Dijkstra and Bellman-Ford.

Answer 2

If you can come up with a good best-first heuristics, I would try using A*

Answer 3

Dijkstra and a simple priority queue should do nicely even for large datasets. If you're practicing, you could try it also with a binary heap and compare performance. Certainly, I think doing a fibonacci heap is a little fringe and would choose to practice on other data structures and algorithms first.

Interestingly, using a priority queue is equivalent to breadth-first search with the heuristic of exploring the current best solution first.

Answer 4

Based on my own experience, I never needed to implement Dijkstra algorithm with a heap in a programming contest. You can get away most of the time, using a slower but efficient enough algorithm. You might use a best Dijkstra implementation to solve a problem which expects a different/simpler algorithm, but this is rare the case.

Answer 5

You can implement Dijkstra using heaps/priority queues without decrease-key in (I think) O((E+V)log V). If you want to decrease key simply add the new entry to your priority queue (leaving the old entry still in the queue) and update your array with distances. When you take the minimum element out of your queue first check that it is equal to your distance array, if it isn't then it was a key you wanted to decrease so just ignore it.