Page 49 - 4336

4.2.2 ААлгориттм Белммана-ФФорда пошуку найкороотшогоо

шляяху

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

відссутностіі від’ємнних доввжин дууг графаа. До якких резуультатівв

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

від’’ємнимии? Для прикладуу, розгляянемо грраф, зобрраженийй на рис..

4.5.. У даному граффі найкорротшим шляхомм, що з’єдєднує верршини vv

та ww, є шляях, що сккладаєтьься з дугг (v, а) таа (a, w). Довжинна цьогоо

шляяху рівнна 2-2==0. Можжна легкко перееконатиссь у тоому, щоо

алгооритм Дейкстрри, будуучи засстосованний до даного графа,,

поммилково вкаже вв якості найкороотшого шшлях, щщо складається зз

дугги (v, w)). Такимм чиномм, немаєє ніякої гарантіїії, що аллгоритмм

Деййкстри ббуде знааходити найкоротший шшлях у випадкаах, колии

доввжини дууг можутть бути ввід’ємниими.

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

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

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

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

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

Рисунокк 4.5.

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

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

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

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

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

49