Алгоритм Флойда-Уоршелла

З алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вершин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. І це вірно. Питання лише в часі виконання такого алгоритму, оскільки його оцінка буде O(n3). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.

Уявімо собі, що до вершин заданого графа прив'язано гумову мотузку. Спочатку будемо вважати, що відстанню між вершинами і та у є довжина цієї мотузки. Але якщо ми її розтягнемо і зачепимо за вершину k, то тепер відстань між вершинами і та j можна вирахувати як суму довжин між вершинами і, k та k, j.

Якщо ця сумарна відстань через вершину виявиться меншою, то надалі необхідно враховувати саме її. Отже, ми отримали ту саму формулу, що і в алгоритмі Дейкстри: di, j = min(di,j, di,k + dk,j).

А тепер запишемо сам алгоритм:

1. Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та у.

2. Визначити вершину і = 1.

3. Визначити вершину j = 1.

4. Якщо величина dj,k + dk,j менша за значення di,j то замінити значення di,j на di,k + dk,j. В іншому разі залишити значення di,j без змін.

5. Якщо j <= п, то перейти до наступної вершини j + 1 і повернутися до п. 4.

6. Якщо і <= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.

7. Якщо k<=n, то перейти до наступної вершини k + 1 і повернутися до п. 2.

8. Завершити алгоритм.

У результаті виконання алгоритму елементи di,j будуть містити найкоротшу відстань між відповідними вершинами графа і та j.

        //Алгоритм Флойда-Уоршелла

        For k := 1 To N   do

          For i := 1 To N   do

            For j := 1 To N  do

                If d[i, j] > d[i, k] + d[k, j] Then

                  d[i, j] := d[i, k] + d[k, j];

Як бачимо, алгоритм найпростіший як у розумінні, так і в його реалізації. Єдине, що слід обов'язково зазначити, це те, що за даним алгоритмом не можна визначити шлях між вершина­ми і та у, який дає визначений найкращий результат. Тому, як­що умова задачі вимагає цієї інформації, то слід все-таки засто­сувати алгоритм Дейкстри для кожної вершини заданого графа.
Завершимо ознайомлення з алгоритмом Флойда-Уоршелла однією практичною порадою. Під час реалізації алгоритму у вигляді програми слід підібрати таке значення елементівd[i, j], що відповідає поняттю «безмежність», тобто відсутність ребра між вершинами і та у.
Нагадаємо оцінку алгоритму Флойда-Уоршелла, яка була дана на початку. Вона становить O(n3) і визначається за кіль­кістю вкладених циклів, що реалізують описаний алгоритм.
Для тестування алгоритму Флойда-Уоршелла можна ви­користати ті самі тести що й для алгоритму Дейкстри. Це дасть змогу перевірити коректність роботи обох алгоритмів.