Page 55 - 4336

вершин. Звичайно, ця більш узагальнена задача могла б бути

вирішена шляхом багаторазового застосування алгоритму

Дейкстри чи Белмана-Форда з послідовним вибором кожної

вершини графа в якості вершини v. Однак реалізація відповідної

процедури вимагала б порівняно більших обчислювальних

витрат. Проте, існують алгоритми більш ефективні, чим

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

Белмана-Форда. Далі розглядаються два досить схожі алгоритми

пошуку на графі найкоротших шляхів між усіма парами вершин.

Ці алгоритми належать Роберту Флойду, Стівену Уоршолу

(алгоритм Флойда-Уоршола) та Джорджу Данцигу (алгоритм

Данцига). В обох алгоритмах для довжин дуг допускаються

від'ємні значення, однак не допускається наявність контурів

від'ємні довжини.

Перш ніж представляти алгоритми, необхідно ввести деякі

позначення. Занумеруємо вершини вхідного графа цілими

числами від 1 до N. Позначимо через довжину найкоротшого
,
шляху з вершини i у вершину j, який у якості проміжних може

містити тільки перші m вершин графа (нагадаємо, що проміжною

вершиною шляху є будь-яка приналежна йому вершина, що не

збігається з його початковою або кінцевою вершинами). Якщо

між вершинами i та j не існує жодного шляху зазначеного типу,

то умовно будемо вважати, що , ∞. З даного визначення

величин випливає, що величина представляє довжину
,
,
найкоротшого шляху з вершини i у вершину j, що не має
проміжних вершин, тобто довжину найкоротшої дуги, що з'єднує

i з j (якщо така дуга присутня в графі). Для будь-якої вершини i

55