🗺️ Флойд-Уоршелл — найкоротші шляхи між усіма парами

Повзунок «Вершини» (від 5 до 7) визначає кількість вузлів у випадковому графі, що також задає розмір матриці відстаней і кількість опорних вершин, через які пройде алгоритм. «Швидкість» (від 0,2 до 4) керує тим, наскільки швидко «Відтворити» автоматично просувається через кроки релаксації; вона не впливає на «Крок», який завжди виконує релаксації рівно для однієї опорної вершини за клік.

«Відтворити» запускає алгоритм безперервно з обраною швидкістю, просуваючи i, j і врешті-решт опорну вершину k, поки всі опорні вершини не будуть оброблені й виконання не позначиться як «Завершено». «Крок» натомість просувається через одну цілу опорну вершину k за один клік, застосовуючи всі її релаксації (i, j) одразу, що корисно для паузи й огляду матриці між опорними вершинами.

Ви обираєте джерело й ціль зі спадних списків. Коли виконання завершується, симуляція відновлює шлях, слідуючи матрицею наступного переходу від джерела до досягнення цілі, і малює кожне ребро цього маршруту фіолетовим кольором на графі, а показник «Відстань шляху» відображає загальну вагу або символ нескінченності, якщо шляху не існує.

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

«Регенерувати» будує новий випадковий орієнтований граф: з'єднане кільце, щоб кожна вершина могла досягти наступної, плюс кілька додаткових випадкових ребер з вагами від 1 до 9, тож форма задачі змінюється щоразу. Зміна повзунка «Вершини» також запускає повну регенерацію, оскільки розмір матриці та довжина кільця залежать від кількості вершин.

Флойд-Уоршелл обчислює найкоротший шлях між кожною парою вершин у зваженому графі одразу. Замість запуску алгоритму з одним джерелом для кожного вузла, він заповнює матрицю відстаней 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.