Алгоритм Беллмана — Форда: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Bsivko (обсуждение | вклад) карточка |
Дима74 (обсуждение | вклад) м ё |
||
Строка 40:
'''return''' <math>d</math>
Здесь ''V'' — множество вершин графа ''G'', ''E'' — множество его рёбер, а ''w'' — весовая функция, заданная на
Внешний цикл выполняется <math>|V| - 1</math> раз, поскольку кратчайший путь не может содержать большее число
Вместо массива ''d'' можно хранить всю матрицу A, но это требует ''O(V²)'' памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу ''P<sub>ij</sub>''.
Строка 60:
<math>P_{vi} \gets u</math>
После выполнения этого алгоритма элементы <math>A_{i, j}</math> содержат длины кратчайших путей от ''s'' до ''i'' с количеством
'''while''' <math>j > 0</math>
| |||