Алгоритм Беллмана — Форда: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Строка 32:
'''return''' <math>d</math>
Здесь ''V'' — множество вершин графа ''G'', ''E'' — множество его рёбер, а ''w'' — весовая функция, заданная на ребрах графа (возвращает длину дуги ведущей из вершины ''v'' в ''u''), d - массив, содержащий расстояния от вершины s до любой другой вершины.
Внешний цикл выполняется <math>|V| - 1</math> раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.
| |||