Алгоритм Беллмана — Форда: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Нет описания правки |
|||
Строка 31:
'''return''' <math>d</math>
Здесь ''V'' — множество вершин графа ''G'', ''E'' — множество его рёбер, а ''w'' — весовая функция, заданная на ребрах графа (возвращает длину [[:ru:Дуга_(теория_графов)#.D0.B4.D1.83.D0.B3.D0.B0|дуги]] ведущей из вершины ''
Внешний цикл выполняется <math>|V| - 1</math> раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.
| |||