编程竞赛最好的单源最短路径算法是什么？

Question

我是从UVa问题集中做this graph problem的。这是一个没有负边权重的单源最短路径问题。据我所知，对于此类问题，具有最佳大O运行时间的算法是Dijkstra，使用斐波那契堆作为优先级队列，尽管实际上二进制堆更容易实现，并且工作得也很好。

然而，似乎即使是二进制堆也需要相当长的时间才能滚动，而且在比赛中时间是有限的。我知道STL提供了一些堆算法和优先级队列，但它们似乎没有提供Dijkstra需要的减键函数。还是我说错了？

似乎另一种可能性是不使用Dijkstra的，This forum thread有人声称他们用广度优先搜索/贝尔曼-福特解决了上面的问题，这更容易编码。(编辑: OTOH，Dijkstra的优先级队列超时的未排序数组。)BFS/Bellman-Ford的工作让我有点惊讶，因为我认为输入规模相当大。我猜不同的问题需要不同复杂度的解决方案，但我的问题是，在这样的比赛中，我需要使用Dijkstra's的频率是多少？我是否应该在更简单但更慢的算法上进行更多的练习？

Answer 1

根据我自己的经验，我从来不需要在编程比赛中使用堆来实现Dijkstra算法。您可以使用较慢但足够有效的算法，在大多数情况下逃脱。您可能会使用最好的Dijkstra实现来解决需要不同/更简单算法的问题，但这种情况很少见。

Answer 2

如果您能想出一个很好的最佳优先启发式，我会尝试使用A*

Answer 3

你可以使用堆/优先级队列来实现Dijkstra，而不需要在(我认为) O((E+V)log )中减少键。如果您想减少key，只需将新条目添加到您的优先级队列中(保留旧条目仍在队列中)，并使用距离更新数组。当你从你的队列中取出最小元素时，首先检查它是否等于你的距离数组，如果不是，那么它就是你想要减少的键，所以忽略它。