Визначення найкоротшого шляху за алгоритмом Флойда
Основна ідея алгоритму Флойда полягає в наступному: нехай є три вершини графа i, j і k, які поєднані між собою ребрами заданої довжини.

Трикутний оператор Флойда
Якщо виконується нерівність , то доцільно замінити маршрут від вершини i до вершини k (
) маршрутом
. Така заміна (іншими словами трикутний оператор) виконується в процесі виконання алгоритму Флойда.
Алгоритм Флойда складається з n етапів (де n кількість вершин графа).
Етап 0: на даному етапі визначаємо початкову матрицю відстаней і матрицю послідовності вершин
. Діагональні елементи обох матриць в обчисленні не беруть участь, тому позначаємо їх символом «-». Також на даному етапі покладають
.
Етап k: на k-му кроці рядок і стовбець під номерок k, являються ведучим рядок і стовбцем. Для кожного елемента матриці
, за умови, що виконується наступна нерівність:
виконуємо наступні дії:
- Створюємо матрицю
, шляхом заміни в матриці
елемента
наступною сумою
.
- Створюємо матрицю
, замінюючи в матриці
елемент
на k.
Розглянемо даний процес більш детально. Нехай на(k-1)-му кроці матрицямає вигляд.
Для елементів даної матриці виконуємо трикутний оператор наступним чином: якщо сума елементів ведучого рядка і колонки (виділені жирним шрифтом) менша ніж значення елементів, які знаходяться на перетині k-го рядка (ведечий рядок) і k-ї колонки (ведуча колонка), то значення даного елемента замінюємо сумою значень ведучих елементів.
Після виконаня n-го етапу алгоритму Флойда, найкоротший шлях між вузлями i та j з допомогою матриць і
визначається наступним чином:
- Відстань між вузлями i та j рівна значенню елемента
матриці
.
- Проміжні вузли найкоротшого шляху від вершини i до вуршини j визначаються з допомогою матриці
наступним чином: припустимо, що
, тоді отримуємо наступний шлях
.