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



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

正如Sedgewick的书《算法》(第4版)中所实现的那样,Dijkstra的算法基于优先级队列,而Bellman-Ford算法基于纯FIFO队列。然而,在我看来,实现算法不需要选择两种队列类型。还可以用FIFO队列实现Dijkstra算法,用优先级队列实现Bellman-Ford算法。

为什么Dijkstra的算法通常用优先级队列来实现,而Bellman-Ford则用FIFO队列来实现?是否存在功能原因,或者是为了运行时优化?

Dijkstra的算法基于优先级队列

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

Bellman-Ford算法基于纯FIFO队列

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

Dijkstra的算法通常被实现的原因是什么具有优先级队列,Bellman-Ford具有FIFO队列是否存在功能性原因,还是运行时原因优化?

是的,这是运行时优化。

最新更新