После большого количества Googling я обнаружил, что большинство источников говорят, что алгоритм Дейкстры "более эффективен", чем алгоритм Беллмана-Форда. Но при каких обстоятельствах алгоритм Беллмана-Форда лучше, чем алгоритм Дейкстры?
Я знаю, что "лучше" - это широкое утверждение, поэтому я имею в виду, в частности, скорость и пространство, если это применимо. Конечно, есть ситуация, в которой подход Беллмана-Форда лучше, чем подход Дейкстры.
Алгоритм Беллмана-Форда является алгоритмом кратчайшего пути из одного источника, поэтому, когда у вас отрицательный вес ребра, он может обнаружить отрицательные циклы на графике.
Единственное различие между ними состоит в том, что Беллман Форд способен также обрабатывать отрицательные веса, тогда как алгоритм Дейкстры может обрабатывать только положительные значения.
Из вики
Однако алгоритм Дейкстры жадно выбирает узел с минимальным весом, который еще не был обработан, и выполняет этот процесс релаксации на всех его исходящих ребрах; напротив, алгоритм Беллмана – Форда просто ослабляет все ребра и делает это | V | - 1 раз, где | V | количество вершин в графе. В каждом из этих повторений растет число вершин с правильно рассчитанными расстояниями, из чего следует, что в конечном итоге все вершины будут иметь свои правильные расстояния. Этот метод позволяет применять алгоритм Беллмана – Форда к более широкому классу входных данных, чем Дейкстра.
Тем не менее, Dijkstra, как правило, считается лучшим в отсутствие отрицательных весовых граней, поскольку типичная реализация очереди приоритетов двоичной кучи имеет O ((| E | + | V |) log | V |) сложность времени [Очередь приоритетов кучи Фибоначчи дает O ( | V | log | V | + | E |)], в то время как алгоритм Беллмана-Форда имеет сложность O (| V || E |)
Единственное различие заключается в том, что алгоритм Дейкстры не может обрабатывать отрицательные веса ребер, которые обрабатывает Беллман-Форд. И звонок-брод также говорит нам, содержит ли график отрицательный цикл. Если граф не содержит отрицательных ребер, тогда Dijkstra всегда лучше.
Эффективной альтернативой Bellman-ford является ациклический график (DAG), который использует топологическую сортировку.
http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
Как уже было указано в выбранном ответе, Bellman-Ford выполняет проверку всех вершин, Дейкстра - только на той, которая рассчитана на лучшее расстояние. Снова уже отмечалось, что улучшает сложность подхода Дейкстры, однако для этого необходимо сравнить все узлы, чтобы узнать минимальное значение расстояния. Если это не нужно в Bellman-Ford, его проще реализовать в распределенной среде. Именно поэтому он используется в протоколах маршрутизации маршрутизации (например, RIP и IGRP), где используется в основном локальная информация. Чтобы использовать Dijkstra в протоколах маршрутизации, вместо этого сначала необходимо распределить всю топологию, и это то, что происходит в протоколах состояния связи, таких как OSPF и ISIS.
Дейкстра Алго
Dijkstra algo не способен различать Отрицательный вес весового цикла присутствует в графике или нет
1. Положительный вес края: - Dijkstra всегда PASS, если весь вес края в графе положителен
2. Отрицательный край wt. и No -ve edge wt. цикл: - Dijkstra всегда PASS, даже если мы имеем вес некоторых ребер как отрицательный, но цикл NO/цикл в графе с отрицательным весом кромки. [т.е. нет отрицательного диапазона веса края]
3. Отрицательный край wt. и -ve edge wt. цикл: - Dijkstra может PASS/FAIL, даже если у нас есть некоторый вес ребер как отрицательный, а цикл/цикл в графе имеет отрицательный вес края.
Я знаю 4 основных различия: - 1. Сложность времени у Беллмана равна O (VE), а у Дейкстры Алго есть O (ElogV) в случае использования maxheap.
Я не согласен полностью, разница в реализации и сложности, алгоритм Дийсктры быстрее (O (n ^ 2)), но его сложно реализовать, а сложность Bellman Ford - O (n ^ 3), но его проще реализовать.