Флойд-Уоршелл обчислює найкоротший шлях між кожною парою вершин зваженого графа за один прохід. Замість запуску алгоритму з одним джерелом від кожного вузла він заповнює матрицю відстаней V×V, де dist[i][j] — це довжина найкоротшого шляху з i до j. Він працює на орієнтованих та неорієнтованих графах і опрацьовує від'ємні ваги ребер, доки немає від'ємного циклу.

Алгоритм використовує потрійний цикл із зовнішньою опорною вершиною k. Для кожної пари (i, j) він перевіряє, чи коротше пройти з i до k, а потім із k до j, ніж поточний найкращий шлях: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Після того як опорна вершина пройде через усі вузли, буде знайдено кожен найкоротший шлях, що використовує лише проміжні вершини з повного набору.

Є три вкладені цикли, кожен з яких пробігає всі V вершин: опорну вершину k, джерело i та ціль j. Це дає V × V × V = V³ кроків релаксації, тож часова складність становить O(V³). Просторова складність — O(V²) для матриці відстаней, плюс іще O(V²), якщо зберігати матрицю попередників для відновлення шляху.

Після ітерації k значення dist[i][j] містить найкоротший шлях з i до j, якому дозволено проходити лише через проміжні вершини з номерами 1..k. Оскільки опорна вершина k є найзовнішнім циклом, до моменту використання dist[i][k] та dist[k][j] вони вже враховують усі попередні опорні вершини, тож рекурентність завжди будується на оптимальних підрозв'язках. Це класичний інваріант динамічного програмування, що забезпечує коректність алгоритму.

На відміну від Дейкстри, Флойд-Уоршелл припускає від'ємні ваги ребер і все одно повертає коректні найкоротші шляхи. Проте від'ємний цикл означає, що деякі найкоротші шляхи невизначені, бо можна нескінченно ходити по колу, зменшуючи вартість. Від'ємний цикл можна виявити після прогону: якщо будь-який діагональний елемент dist[i][i] стає від'ємним, вершина i лежить на від'ємному циклі. Ця симуляція використовує лише невід'ємні ваги, щоб результати були добре визначеними.

Під час ініціалізації матриця наступного переходу next[i][j] встановлюється в j щоразу, коли існує пряме ребро. Щоразу, коли релаксація через опорну вершину k покращує dist[i][j], ми копіюємо next[i][j] = next[i][k], фіксуючи, що найкращий маршрут тепер починається з руху до k. Щоб відновити шлях, ви прямуєте за next[i][j] від джерела, доки не досягнете цілі, збираючи вершини по дорозі.

Дейкстра розв'язує задачу найкоротшого шляху з одного джерела та швидка на розріджених графах, але потребує невід'ємних ваг і дає шляхи лише з одного джерела. Запуск Дейкстри від кожної вершини коштує близько O(V·E·log V) із купою, що перевершує Флойда-Уоршелла на великих розріджених графах. Флойд-Уоршелл із його рівною вартістю O(V³) та малими константами простіший у написанні й часто виграє на малих або щільних графах і коли вам справді потрібні всі пари.

Беллман-Форд також працює з одним джерелом, але, як і Флойд-Уоршелл, припускає від'ємні ребра й може виявляти від'ємні цикли. Він виконується за O(V·E) на кожне джерело. Якщо вам потрібні найкоротші шляхи з одного початку в графі з від'ємними ребрами, Беллман-Форд є природним вибором; якщо ж потрібні всі пари одразу, три компактні цикли Флойда-Уоршелла зазвичай простіші й конкурентні на щільних графах.

Елемент зі значенням ∞ означає, що наразі між цими двома вершинами немає відомого шляху. Діагональ dist[i][i] починається з 0, бо відстань від вершини до самої себе дорівнює нулю. Коли опорна вершина просувається, елементи ∞ можуть стати скінченними, якщо проміжна вершина з'єднує два раніше роз'єднані вузли — саме це «стискання» матриці ви бачите в анімації.

Його використовують для таблиць маршрутизації в невеликих мережах, обчислення транзитивного замикання відношення, пошуку діаметра та центральності графа й розв'язання запитів відстаней між усіма парами в картах, іграх та дослідженні операцій. Булевий варіант обчислює досяжність, а варіант max-min розв'язує задачі найширшого шляху чи вузького місця, замінюючи операції min/plus на max/min.