Визначення найкоротшого шляху за алгоритмом Флойда

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

Якщо виконується нерівність , то доцільно замінити маршрут від вершини i до  вершини k () маршрутом . Така заміна (іншими словами трикутний оператор) виконується в процесі виконання алгоритму Флойда.

Алгоритм Флойда складається з n етапів (де n кількість вершин графа).

Етап 0: на даному етапі визначаємо початкову матрицю відстаней і матрицю послідовності вершин . Діагональні елементи обох матриць в обчисленні не беруть участь, тому позначаємо їх символом «-». Також на даному етапі покладають .

Етап k: на k-му кроці рядок і стовбець під номерок k, являються ведучим рядок і стовбцем. Для кожного елемента матриці , за умови, що виконується наступна нерівність:

виконуємо наступні дії:

1. Створюємо матрицю , шляхом заміни в матриці елемента  наступною сумою .
2. Створюємо матрицю , замінюючи в матриці елемент на k.

Розглянемо даний процес більш детально. Нехай на(k-1)-му кроці матрицямає вигляд.

Для елементів даної матриці виконуємо трикутний оператор наступним чином: якщо сума елементів ведучого рядка і колонки (виділені жирним шрифтом) менша ніж значення елементів, які знаходяться на перетині k-го рядка (ведечий рядок) і k-ї колонки (ведуча колонка), то значення даного елемента замінюємо сумою значень ведучих елементів.

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

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