对于编程竞赛,最好的单源最短路径算法是什么?

根据我自己的经验,我从不需要在编程比赛中用堆实现Dijkstra算法。你可以利用一个速度较慢但效率足够高的算法,在大多数情况下逃走。您可以使用一个最好的dijkstra实现来解决一个需要不同/更简单算法的问题,但这种情况很少发生。

如果你能想出一个好的第一启发式,我会尝试使用 A*

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

这个 Boost Graph Library 似乎对Dijkstra和BellmanFord都有实现。

Dijkstra和一个简单的优先级队列应该可以很好地处理大型数据集。如果您正在练习,也可以使用二进制堆尝试它,并比较性能。当然,我认为做一个斐波那契堆是有点边缘化的,我会选择先在其他数据结构和算法上进行实践。

有趣的是,使用优先级队列相当于广度优先搜索,其启发式方法是先探索当前的最佳解决方案。