单源最短路径实现:优先级与FIFO队列

Question

根据问题的具体情况，在单源最短路径问题中通常提到的两种算法是Dijkstra算法和Bellman算法。Dijkstra的算法工作在正边权值，而Bellman算法是一个推广，也允许负边权。

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

为什么Dijkstra的算法通常是用优先级队列来实现的，Bellman则是用FIFO队列实现的呢？是出于功能原因，还是为了运行时优化？

Answer 1

Dijkstra的算法是基于优先级队列的

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

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

没有任何类型的队列，您可以很容易地实现Bellman算法。下面是一个实现示例。https://kt48.wordpress.com/2015/06/16/bellman-ford-algorithm-c-implementation/

为什么Dijkstra的算法通常是用优先级队列来实现的，Bellman则是用FIFO队列实现的呢？是出于功能原因，还是为了运行时优化？

是的，这是运行时优化。