2 1
1----------2---------4
| | |
|3 |3 |1
| 6 | |
3---------5 ---------
Хорошо, так что это график. Мой источник node - 1, а пункт назначения node - 5
Мой вопрос.
Оба алгоритма будут давать один и тот же результат или нет?
То есть оба возвратятся 1->2->4->5? (За исключением того, что отрицательные веса не допускаются в dijkstra's)
Заранее благодарим за помощь.
Алгоритм Беллмана-Форда является алгоритмом кратчайшего пути с одним источником, который допускает отрицательный вес края и может обнаруживать отрицательные циклы в графике.
Алгоритм Дейкстры также является еще одним алгоритмом кратчайшего пути одного источника. Однако вес всех ребер должен быть неотрицательным.
В вашем случае, что касается общей стоимости, разница не будет, так как ребра на графике имеют отрицательный вес. Однако алгоритм Дейкстры обычно используется, поскольку типичная реализация с бинарной кучей имеет временную сложность Theta((|E|+|V|)log|V|), тогда как алгоритм Беллмана-Форда имеет сложность O(|V||E|).
Если существует более одного пути с минимальными затратами, фактический возвращаемый путь зависит от реализации (даже для одного и того же алгоритма).
Вершины алгоритма Дейкстраса содержат всю информацию о сети. Нет такой вещи, что каждая вершина заботится только о себе и соседях. С другой стороны, узлы алгоритмов Bellman-Ford содержат только информацию, связанную с этим. Эта информация позволяет node просто знать, к каким соседним узлам он может подключиться, и node, что отношение происходит, взаимно. Алгоритм Дейкстраса быстрее, чем алгоритм Беллмана-Форда, однако второй алгоритм может быть более полезным для решения некоторых задач, таких как отрицательные веса путей.