Обгрунтування вибору методу та алгоритму розв’язання задачі. Розглянемо основну ідею, що лежить в основі алгоритму Флойда

Розглянемо основну ідею, що лежить в основі алгоритму Флойда. Суть алгоритму Флойда полягає в перевірці того, чи не виявиться шлях з вершини i у вершину j коротше, якщо він буде проходити через деяку проміжну вершину m. Припустимо, що нам відомі:

1. найкоротший шлях з вершини i у вершину m, в якому в якості проміжних допускається використання тільки перших (m - 1) вершин;
2. найкоротший шлях з вершини m у вершину j, в якому в якості проміжних допускається використання тільки перших (m - 1) вершин;
3. найкоротший шлях з вершини i у вершину j, в якому в якості проміжних допускається використання тільки перших (m - 1) вершин.

Оскільки за припущенням вихідний граф не може містити контурів негативної довжини, один з двох шляхів - шлях, що співпадає з представленим у пункті 3, або шлях, який є об'єднанням шляхів з пунктів 1 і 2 - повинен бути найкоротшим шляхом з вершини i у вершину j, в якому в якості проміжних допускається використання тільки перших m вершин. Таким чином,

d_i,j^m=min{ d_i,m^m-1+ d_m,j^m-1; d_i,j^m-1}

Зі співвідношення видно, що для обчислення елементів матриці Dm необхідно розташовувати лише елементами матриці Dm-1. Більше того, відповідні обчислення можуть бути проведені без звернення до вихідного графу. Тепер мм в стані дати формальний опис алгоритму Флойда для знаходження на графі найкоротших шляхів між усіма парами вершин.

Алгоритм

1. Пронумерувати вершини графа від 1 до N цілими числами, визначити матрицю D0, кожен елемент di, j який є довжиною найкоротшої дуги між вершинами i та j. Якщо такої дуги немає, покласти значення елемента рівним ∞. Крім того, покласти значення діагонального елемента di, рівним 0.
2. Для цілого m, послідовно приймаючого значення 1... N визначити за елементами матриці Dm-1 елементи Dm
3. Алгоритм закінчується отриманням матриці всіх найкоротших шляхів DN, N - число вершин графа.

Нагадаємо, для визначення з відомих елементів матриці Dm-1 елементів матриці Dm в алгоритмі Флойда застосовується рекурсивне співвідношення:

d_i,j^m=min{ d_i,m^m-1+ d_m,j^m-1; d_i,j^m-1}

di, jm - елемент матриці Dm, di, jm-1 - елементи матриці Dm-1 найденої на попередньому кроці алгоритму.