Single Source Shortest Path implementation: priority vs. FIFO queue

Question

Depending on the problem specifics, two algorithms generally mentioned in the context of the single source shortest path problem is Dijkstra's algorithm and the Bellman-Ford algorithm. Dijkstra's algorithm works with positive edge weights, whereas the Bellman-Ford algorithm is a generalization also allowing for negative edge weights.

As implemented in Sedgewick's book "Algorithms" (4th ed.), Dijkstra's algorithm is based on a priority queue, whereas the Bellman-Ford algorithm is based on a plain FIFO queue. However, to me it doesn't look like either choice of the two queue types would be necessary for implementing the algorithms. One could just as well implement Dijkstra's algorithm with a FIFO queue and the Bellman-Ford algorithm with a priority queue.

What is the reason why Dijkstra's algorithm is usually implemented with a priority queue, Bellman-Ford on the other hand with a FIFO queue? Is there a functional reason, or is it for runtime optimization?

Answer 1

Dijkstra's algorithm is based on a priority queue

Not necessarily. You can also implement dijkstra's algorithm without a priority queue. But in that case you have to pick the lowest value after searching from your array of node list you are currently processing.

Bellman-Ford algorithm is based on a plain FIFO queue

Without any sort of queue you can easily implement Bellman-ford algorithm. here is an example implementation. https://kt48.wordpress.com/2015/06/16/bellman-ford-algorithm-c-implementation/

What is the reason why Dijkstra's algorithm is usually implemented with a priority queue, Bellman-Ford on the other hand with a FIFO queue? Is there a functional reason, or is it for runtime optimization?

Yes, it is runtime optimization.