В зависимост от спецификата на проблема, два алгоритъма, които обикновено се споменават в контекста на проблема за най-краткия път с един източник, са алгоритъмът на Дейкстра и алгоритъмът на Белман-Форд. Алгоритъмът на Дейкстра работи с положителни тегла на ръба, докато алгоритъмът на Белман-Форд е обобщение, позволяващо също отрицателни тегла на ръба.
Както е приложено в книгата на Седжуик "Алгоритми" (4-то издание), алгоритъмът на Дейкстра се основава на приоритетна опашка, докато алгоритъмът на Белман-Форд се основава на обикновена FIFO опашка. За мен обаче не изглежда, че изборът на двата типа опашки би бил необходим за прилагане на алгоритмите. Човек може също толкова добре да приложи алгоритъма на Дейкстра с FIFO опашка и алгоритъма на Белман-Форд с приоритетна опашка.
Каква е причината, поради която алгоритъмът на Дайкстра обикновено се прилага с приоритетна опашка, а Bellman-Ford от друга страна с FIFO опашка? Има ли функционална причина или е за оптимизация на времето за изпълнение?
