单源最短路径实现：优先级与先进先出队列

Question

根据具体问题的不同，在单源最短路径问题的背景下一般提到的两种算法是Dijkstra算法和Bellman-Ford算法。 Dijkstra的算法以正边权重工作，而Bellman-Ford算法是一种泛化，也允许负边权重。如在Sedgewick的书“算法”（第4版）中实现的，Dijkstra的算法基于优先级队列，而Bellman-Ford算法基于简单的FIFO队列。 但是，对于我来说，看起来好像两种队列类型的选择对于实现算法都是必需的。用FIFO队列和具有优先队列的Bellman-Ford算法也可以实现Dijkstra算法。

为什么Dijkstra算法通常使用优先级队列来实现，而Bellman-Ford则使用FIFO队列？有没有功能原因，还是运行时优化？

Answer 1

Dijkstra算法是基于优先级队列

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

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

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

究竟是为什么Dijkstra算法通常与优先级队列实现 的原因，贝尔曼 - 福特，另一方面与FIFO队列 ？有没有功能上的原因，还是它对于运行时 优化？

是的，它是运行时优化。