Page 29 - 4387

ЛАБОРАТОРНА РОБОТА № 4

Реалізація алгоритму Белмана-Форда пошуку найкоротшого

шляху

4.1 Мета і завдання роботи роботи

Мета роботи – засвоїти принцип пошуку найкоротшого

шляху між двома заданими вершинами графа за допомогою
алгоритму Белмана-Форда.

Завдання роботи – знайти за допомогою алгоритму
Белмана-Форда найкоротший шлях між двома заданими

вершинами графа.
Тривалість лабораторної роботи – 4 год. (2 пари).

4.2 Основні теоретичні положення

Вхідне припущення в алгоритмі Дейкстри полягало у

відсутності від’ємних довжин дуг графа. Тому, немає ніякої

гарантії, що алгоритм Дейкстри буде знаходити найкоротший

шлях у випадках, коли довжини дуг можуть бути від’ємними.

Алгоритм Дейкстри може бути узагальнений на випадок,

коли деякі з дуг мають від’ємні довжини. Ідею відповідного

узагальнення запропонували незалежно американські математики

Лестер Форд у 1956 р. та Річард Белман у 1958 р. Необхідна

модифікація алгоритму Дейкстри полягає в такому.

1. На кроці 2 алгоритму перерахування величин d(x) за

допомогою співвідношення (3.1) проводиться для усіх вершин

(крім позначеної на попередньому етапі), а не тільки для

непозначених. Отже, числа d(x) можуть зменшуватися як для

непозначених, так і для позначених вершин.

28