queue - 单源最短路径实现：优先级与 FIFO 队列

Question

根据问题的具体情况，在单源最短路径问题的上下文中通常提到的两种算法是 Dijkstra 算法和 Bellman-Ford 算法。Dijkstra 算法适用于正边权重，而 Bellman-Ford 算法是一种泛化，也允许负边权重。

正如 Sedgewick 的“算法”一书（第 4 版）中所实现的，Dijkstra 的算法基于优先级队列，而 Bellman-Ford 算法基于普通的 FIFO 队列。但是，在我看来，这两种队列类型中的任何一种选择都不是实现算法所必需的。人们也可以用 FIFO 队列实现 Dijkstra 算法，用优先级队列实现 Bellman-Ford 算法。

为什么 Dijkstra 的算法通常使用优先级队列来实现，而贝尔曼福特算法通常使用 FIFO 队列来实现？有功能原因，还是运行时优化？

Answer 1

Dijkstra 算法基于优先级队列

不必要。您还可以在没有优先级队列的情况下实现 dijkstra 算法。但在这种情况下，您必须在从当前正在处理的节点列表数组中搜索后选择最小值。

Bellman-Ford 算法基于一个普通的 FIFO 队列

无需任何队列，您就可以轻松实现 Bellman-ford 算法。这是一个示例实现。https://kt48.wordpress.com/2015/06/16/bellman-ford-algorithm-c-implementation/

为什么 Dijkstra 的算法通常使用优先级队列来实现，而贝尔曼福特算法通常使用 FIFO 队列来实现？有功能原因，还是运行时优化？

是的，它是运行时优化。