Page 54 - 4336

Слід зазначити, що алгоритм Белмана-Форда не знаходить

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

графі наявний контур з від'ємною довжиною. В такому випадку,

“повторюючи” такий контур нескінченну кількість раз, можна

одержати шлях із як завгодно малою по величині довжиною.

У випадку, якщо немає відомостей про наявність чи

відсутність у графі, що розглядається, контурів від’ємної

довжини, можна використовувати алгоритм Белмана-Форда, але в

процесі його роботи необхідно враховувати скільки разів

позначається окрема вершина. Як тільки будь-яка із вершин

позначається n-й раз, де n кількість вершин графа, процедуру

алгоритму можна зупинити – вхідний граф містить контур

від'ємної довжини. В іншому випадку процедура алгоритму

Белмана-Форда завершується за скінченне число кроків,

правильно вирішуючи поставлену задачу.

Для обґрунтування наведеного правила припустимо, що

вхідний граф не містить контурів від'ємної довжини. Тоді якщо в

деякої вершини x величина d(x) набуває остаточного значення

(тобто визначається довжина найкоротшого шляху з v у x), то в

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

позначена знову (або вперше) тільки один раз, перш ніж буде

остаточно позначена одна з них. Таким чином, жодна з вершина

не може бути позначена більш n-1 раз.

4.3 Алгоритми пошуку всіх найкоротших шляхів

У підрозділах 4.2.1 та 4.2.2 розглядалась задача знаходження

на графі найкоротшого шляху з деякої виділеної вершини до

будь-якої іншої вершини. У даному підрозділі буде розглянута

задача пошуку на графі найкоротшого шляху між кожною парою

54