Алгоритм Беллмана — Форда: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Bosik GN (обсуждение | вклад) м →Решение задачи на графе без отрицательных циклов: оформление |
Bosik GN (обсуждение | вклад) м →Формулировка задачи: оформление |
||
Строка 9:
Дан ориентированный или неориентированный [[Граф (математика)|граф]] ''G'' со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины ''s'' до всех вершин графа.
Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется
== Решение задачи на графе без отрицательных циклов ==
| |||