Разница между алгоритмом Bellman Ford и Dijkstra 

   2           1
1----------2---------4
|          |         |
|3         |3        |1
|    6     |         |
3---------5 ---------

Хорошо, так что это график. Мой источник node - 1, а пункт назначения node - 5

Мой вопрос.

Оба алгоритма будут давать один и тот же результат или нет? То есть оба возвратятся 1->2->4->5? (За исключением того, что отрицательные веса не допускаются в dijkstra's)

Заранее благодарим за помощь.

Ответы

Ответ 1

Алгоритм Беллмана-Форда является алгоритмом кратчайшего пути с одним источником, который допускает отрицательный вес края и может обнаруживать отрицательные циклы в графике.

Алгоритм Дейкстры также является еще одним алгоритмом кратчайшего пути одного источника. Однако вес всех ребер должен быть неотрицательным.

В вашем случае, что касается общей стоимости, разница не будет, так как ребра на графике имеют отрицательный вес. Однако алгоритм Дейкстры обычно используется, поскольку типичная реализация с бинарной кучей имеет временную сложность Theta((|E|+|V|)log|V|), тогда как алгоритм Беллмана-Форда имеет сложность O(|V||E|).

Если существует более одного пути с минимальными затратами, фактический возвращаемый путь зависит от реализации (даже для одного и того же алгоритма).

Ответ 2

Вершины алгоритма Дейкстраса содержат всю информацию о сети. Нет такой вещи, что каждая вершина заботится только о себе и соседях. С другой стороны, узлы алгоритмов Bellman-Ford содержат только информацию, связанную с этим. Эта информация позволяет node просто знать, к каким соседним узлам он может подключиться, и node, что отношение происходит, взаимно. Алгоритм Дейкстраса быстрее, чем алгоритм Беллмана-Форда, однако второй алгоритм может быть более полезным для решения некоторых задач, таких как отрицательные веса путей.