Алгоритм Беллмана — Форда: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Bosik GN (обсуждение | вклад) м →Граф с отрицательными циклами: стилевые правки |
Bosik GN (обсуждение | вклад) м →Решение задачи на графе без отрицательных циклов: оформление |
||
Строка 15:
Для нахождения кратчайших путей от одной вершины до всех остальных, воспользуемся методом [[Динамическое программирование|динамического программирования]]. Построим [[Матрица (математика)|матрицу]] A<sub>ij</sub>, элементы которой будут обозначать следующее:
A<sub>ij</sub> — это <b>длина кратчайшего пути из ''s'' в ''i''</b>, содержащего не более ''j'' рёбер.
Путь, содержащий 0 рёбер, существует только до вершины ''s''. Таким образом, A<sub>i0</sub> равно 0 при ''i'' = ''s'', и +∞ в противном случае.
| |||