В зависимости от специфики проблемы в контексте задачи о кратчайшем пути с одним источником обычно упоминаются два алгоритма: алгоритм Дейкстры и алгоритм Беллмана-Форда. Алгоритм Дейкстры работает с положительными весами ребер, тогда как алгоритм Беллмана-Форда является обобщением, также допускающим отрицательные веса ребер.
Как реализовано в книге Седжвика «Алгоритмы» (4-е изд.), Алгоритм Дейкстры основан на очереди с приоритетами, тогда как алгоритм Беллмана-Форда основан на простой очереди FIFO. Однако мне не кажется, что для реализации алгоритмов потребуется какой-либо выбор из двух типов очереди. С таким же успехом можно реализовать алгоритм Дейкстры с очередью FIFO и алгоритм Беллмана-Форда с очередью с приоритетом.
По какой причине алгоритм Дейкстры обычно реализуется с приоритетной очередью, а алгоритм Беллмана-Форда с другой стороны - с очередью FIFO? Есть ли функциональная причина или это для оптимизации времени выполнения?
