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