Алгоритм Беллмана — Форда: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
м откат правок 178.213.240.13 (обс.) к версии Дима74 Метка: откат |
|||
Строка 68:
'''return''' ''p''
== Граф с отрицательными циклами ==
Алгоритм Беллмана-Форда позволяет очень просто определить, существует ли в графе <math>G</math> отрицательный цикл, достижимый из вершины <math>s</math>. Достаточно произвести внешнюю итерацию цикла не <math>|V| - 1</math>, a ровно <math>|V|</math> раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из <math>s</math>.
На основе этого можно предложить следующую оптимизацию: отслеживать изменения в графе и, как только они закончатся, сделать выход из цикла (дальнейшие итерации будут бессмысленны).
== Литература ==
| |||