Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що робить алгоритм Беллмана-Форда?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Алгоритм Беллмана-Форда** - це алгоритм пошуку **найкоротших шляхів від однієї вершини до всіх інших**, який, на відміну від Дейкстри, **працює навіть із від'ємними вагами ребер**. **Ключове:** алгоритм Беллмана-Форда - єдиний базовий алгоритм, який може виявити від'ємні цикли.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Алгоритм Беллмана-Форда** - це алгоритм пошуку **найкоротших шляхів від однієї вершини до всіх інших**, який, на відміну від Дейкстри, **працює навіть із від'ємними вагами ребер**. --- ### Ідея Він багаторазово «розслаблює» (оновлює) всі ребра графа, поки відстані до всіх вершин не стабілізуються. «Розслабити ребро» (u → v) з вагою **w** означає: якщо через u можна потрапити в v **дешевше**, ніж раніше, то оновлюємо: [ dist[v] = dist[u] + w ] --- ### Як це працює 1. Задати відстань до всіх вершин = ∞, крім стартової (0). 2. Повторити **|V| - 1 раз** (де |V| - число вершин): - Для кожного ребра (u, v, w): якщо **dist[u] + w < dist[v]**, оновити **dist[v]**. 3. Після цього зробити ще один прохід: - Якщо на якомусь ребрі відстань усе ще можна зменшити, значить, є **від'ємний цикл** (шлях, що зменшує відстань нескінченно). --- ### Приклад Нехай ребра: A → B (4), A → C (5), B → C (-3) 1. Старт: dist[A]=0, dist[B]=∞, dist[C]=∞ 2. Після 1-ї ітерації: - dist[B] = 4 - dist[C] = 5 3. Розслаблюємо B→C: dist[C] = 4 + (-3) = 1 → найкоротший шлях A → B → C = 1 --- ### Складність - Час: **O(V × E)** - Пам'ять: **O(V)** --- ### Переваги - Працює з від'ємними вагами. - Може **виявити від'ємні цикли**. ### Недоліки - Повільніший, ніж алгоритм Дейкстри. --- **Підсумок:** Алгоритм Беллмана-Форда - це універсальний спосіб знайти найкоротші шляхи, навіть якщо в графі є від'ємні ваги, і єдиний базовий алгоритм, який може **виявити від'ємні цикли**.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.