Алгоритм Флойда–Воршелла

Задано орієнтований або неорієнтований зважений граф $G$ з $n$ вершинами. Потрібно знайти довжину найкоротшого шляху $d_{ij}$ між кожною парою вершин $i$ та $j$.

Граф може містити ребра від'ємної ваги, але не повинен містити циклів від'ємної ваги.

Якщо такий від'ємний цикл існує, ми можемо обходити його знову й знову, на кожній ітерації роблячи вартість шляху меншою. Отже, ми можемо зробити деякі шляхи як завгодно малими, або, іншими словами, найкоротший шлях стає невизначеним. Це автоматично означає, що неорієнтований граф не може мати жодного ребра від'ємної ваги, адже таке ребро вже саме по собі утворює від'ємний цикл, оскільки ми можемо рухатися туди-сюди вздовж цього ребра скільки завгодно разів.

Цей алгоритм також можна використати для виявлення наявності від'ємних циклів. Граф містить від'ємний цикл, якщо наприкінці роботи алгоритму відстань від деякої вершини $v$ до самої себе є від'ємною.

Цей алгоритм був одночасно опублікований у статтях Роберта Флойда та Стівена Воршелла у 1962 році. Однак ще у 1959 році Бернар Руа опублікував по суті той самий алгоритм, але його публікація залишилася непоміченою.

Коли підходить цей алгоритм?

• Потрібні найкоротші шляхи між усіма парами вершин, а не з однієї? (якщо лише з однієї вершини → Дейкстра або Беллман-Форд)
• Кількість вершин мала, $V \lesssim 500$, щоб витримати $O(V^3)$? (для розрідженого графа з багатьма вершинами краще запустити Дейкстру з кожної вершини)
• Граф може містити ребра від'ємної ваги (але без від'ємних циклів), або потрібна транзитивна досяжність / детекція від'ємного циклу?

Опис алгоритму

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

Пронумеруємо вершини від 1 до $n$. Матрицю відстаней позначимо $d[ ][ ]$.

Перед $k$-ю фазою ($k = 1 \dots n$) значення $d[i][j]$ для будь-яких вершин $i$ та $j$ зберігає довжину найкоротшого шляху між вершиною $i$ та вершиною $j$, який як проміжні вершини містить лише вершини зі множини $\{1, 2, ..., k-1\}$.

Іншими словами, перед $k$-ю фазою значення $d[i][j]$ дорівнює довжині найкоротшого шляху від вершини $i$ до вершини $j$, якщо цьому шляху дозволено заходити лише у вершини з номерами, меншими за $k$ (початок і кінець шляху цією умовою не обмежені).

Легко переконатися, що ця властивість виконується для першої фази. Для $k = 0$ ми можемо заповнити матрицю так: $d[i][j] = w_{i j}$, якщо існує ребро між $i$ та $j$ з вагою $w_{i j}$, і $d[i][j] = \infty$, якщо такого ребра не існує. На практиці $\infty$ буде деяким великим значенням. Як ми побачимо далі, це є вимогою алгоритму.

Припустимо тепер, що ми перебуваємо на $k$-й фазі й хочемо обчислити матрицю $d[ ][ ]$ так, щоб вона задовольняла вимоги для $(k + 1)$-ї фази. Нам потрібно уточнити відстані для деяких пар вершин $(i, j)$. Тут є два принципово різні випадки:

• Найкоротший шлях від вершини $i$ до вершини $j$ з проміжними вершинами зі множини $\{1, 2, \dots, k\}$ збігається з найкоротшим шляхом з проміжними вершинами зі множини $\{1, 2, \dots, k-1\}$.

  У цьому випадку $d[i][j]$ під час переходу не зміниться.

• Найкоротший шлях з проміжними вершинами зі множини $\{1, 2, \dots, k\}$ є коротшим.

  Це означає, що новий, коротший шлях проходить через вершину $k$. Це означає, що ми можемо розбити найкоротший шлях між $i$ та $j$ на два шляхи: шлях між $i$ та $k$ і шлях між $k$ та $j$. Зрозуміло, що обидва ці шляхи використовують лише проміжні вершини зі множини $\{1, 2, \dots, k-1\}$ і є найкоротшими такими шляхами у цьому сенсі. Тому ми вже обчислили довжини цих шляхів раніше й можемо обчислити довжину найкоротшого шляху між $i$ та $j$ як $d[i][k] + d[k][j]$.

Поєднуючи ці два випадки, ми бачимо, що можемо перерахувати довжину для всіх пар $(i, j)$ на $k$-й фазі у такий спосіб:

$$d_{\text{new}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

Таким чином, уся робота, потрібна на $k$-й фазі, — це перебрати всі пари вершин і перерахувати довжину найкоротшого шляху між ними. У результаті після $n$-ї фази значення $d[i][j]$ у матриці відстаней є довжиною найкоротшого шляху між $i$ та $j$, або дорівнює $\infty$, якщо шляху між вершинами $i$ та $j$ не існує.

Останнє зауваження — нам не потрібно створювати окрему матрицю відстаней $d_{\text{new}}[ ][ ]$ для тимчасового зберігання найкоротших шляхів $k$-ї фази, тобто всі зміни можна вносити безпосередньо в матрицю $d[ ][ ]$ на будь-якій фазі. Насправді на будь-якій $k$-й фазі ми лише покращуємо відстань для будь-якого шляху в матриці відстаней, тож не можемо погіршити довжину найкоротшого шляху для жодної пари вершин, які мають оброблятися на $(k+1)$-й чи пізнішій фазі.

Часова складність цього алгоритму, очевидно, дорівнює $O(n^3)$.

Реалізація

Нехай $d[][]$ — це двовимірний масив розміру $n \times n$, який заповнено відповідно до $0$-ї фази, як пояснено раніше. Також на $0$-й фазі ми покладемо $d[i][i] = 0$ для будь-якого $i$.

Тоді алгоритм реалізується так:

C++

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Python

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

TypeScript

for (let k = 0; k < n; ++k) {
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

Go

for k := 0; k < n; k++ {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if d[i][k]+d[k][j] < d[i][j] {
                d[i][j] = d[i][k] + d[k][j]
            }
        }
    }
}

Передбачається, що якщо між якимись двома вершинами $i$ та $j$ немає ребра, то в матриці $d[i][j]$ міститься велике число (достатньо велике, щоб воно перевищувало довжину будь-якого шляху в цьому графі). Тоді брати таке ребро завжди буде невигідно, і алгоритм працюватиме коректно.

Однак якщо в графі є ребра від'ємної ваги, потрібно вжити особливих заходів. Інакше отримані значення в матриці можуть мати вигляд $\infty - 1$, $\infty - 2$ тощо, що, звісно, все одно означає, що між відповідними вершинами шляху не існує. Тому, якщо граф містить ребра від'ємної ваги, краще записати алгоритм Флойда–Воршелла у такий спосіб, щоб він не виконував переходи через шляхи, яких не існує.

C++

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

Python

for k in range(n):
    for i in range(n):
        for j in range(n):
            # не робимо перехід через неіснуючі шляхи,
            # інакше отримали б некоректні відстані виду INF - 1
            if d[i][k] < INF and d[k][j] < INF:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

TypeScript

for (let k = 0; k < n; ++k) {
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            // не робимо перехід через неіснуючі шляхи,
            // інакше отримали б некоректні відстані виду INF - 1
            if (d[i][k] < INF && d[k][j] < INF) {
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

Go

for k := 0; k < n; k++ {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            // не робимо перехід через неіснуючі шляхи,
            // інакше отримали б некоректні відстані виду INF - 1
            if d[i][k] < INF && d[k][j] < INF && d[i][k]+d[k][j] < d[i][j] {
                d[i][j] = d[i][k] + d[k][j]
            }
        }
    }
}

Відновлення послідовності вершин найкоротшого шляху

Легко підтримувати додаткову інформацію, за допомогою якої можна буде відновити найкоротший шлях між будь-якими двома заданими вершинами у вигляді послідовності вершин.

Для цього, на додачу до матриці відстаней $d[ ][ ]$, потрібно підтримувати матрицю предків $p[ ][ ]$, яка міститиме номер фази, на якій найкоротша відстань між двома вершинами востаннє змінювалася. Зрозуміло, що цей номер фази — це не що інше, як вершина посередині шуканого найкоротшого шляху. Тепер нам потрібно лише знайти найкоротший шлях між вершинами $i$ та $p[i][j]$, а також між $p[i][j]$ та $j$. Це приводить до простого рекурсивного алгоритму відновлення найкоротшого шляху.

Випадок дійсних ваг

Якщо ваги ребер не цілі, а дійсні, потрібно враховувати похибки, які виникають під час роботи з типами з рухомою комою.

Алгоритм Флойда–Воршелла має неприємну особливість: похибки накопичуються дуже швидко. Насправді, якщо на першій фазі виникає похибка $\delta$, то на другій ітерації ця похибка може поширитися як $2 \delta$, на третій ітерації — як $4 \delta$ і так далі.

Щоб цього уникнути, алгоритм можна модифікувати так, аби він враховував похибку (EPS = $\delta$), використовуючи таке порівняння:

C++

if (d[i][k] + d[k][j] < d[i][j] - EPS)
    d[i][j] = d[i][k] + d[k][j]; 

Python

if d[i][k] + d[k][j] < d[i][j] - EPS:
    d[i][j] = d[i][k] + d[k][j]

TypeScript

if (d[i][k] + d[k][j] < d[i][j] - EPS) {
    d[i][j] = d[i][k] + d[k][j];
}

Go

if d[i][k]+d[k][j] < d[i][j]-EPS {
    d[i][j] = d[i][k] + d[k][j]
}

Випадок від'ємних циклів

Формально алгоритм Флойда–Воршелла не застосовний до графів, які містять цикл(и) від'ємної ваги. Але для всіх пар вершин $i$ та $j$, для яких не існує шляху, що починається в $i$, проходить через від'ємний цикл і закінчується в $j$, алгоритм усе одно працюватиме коректно.

Для пари вершин, для якої відповіді не існує (через наявність від'ємного циклу на шляху між ними), алгоритм Флойда збереже в матриці відстаней якесь число (можливо, дуже від'ємне, але не обов'язково). Однак алгоритм Флойда–Воршелла можна вдосконалити так, щоб він акуратно обробляв такі пари вершин і виводив їх, наприклад, як $-\text{INF}$.

Це можна зробити так: запустимо звичайний алгоритм Флойда–Воршелла для заданого графа. Тоді найкоротший шлях між вершинами $i$ та $j$ не існує тоді й лише тоді, коли існує вершина $t$ така, що $t$ досяжна з $i$, а $j$ досяжна з $t$, і для якої $d[t][t] < 0$.

Крім того, використовуючи алгоритм Флойда–Воршелла для графів із від'ємними циклами, ми маємо пам'ятати, що можуть виникати ситуації, коли відстані експоненційно швидко спадають у від'ємну область. Тому переповнення цілих чисел потрібно обробляти, обмежуючи мінімальну відстань деяким значенням (наприклад, $-\text{INF}$).

Щоб дізнатися більше про пошук від'ємних циклів у графі, дивіться окрему статтю Пошук від'ємного циклу в графі.

Задачі для практики

• UVA: Page Hopping
• SPOJ: Possible Friends
• CODEFORCES: Greg and Graph
• SPOJ: CHICAGO - 106 miles to Chicago

• UVA 10724 - Road Construction
• UVA 117 - The Postal Worker Rings Once
• Codeforces - Traveling Graph
• UVA - 1198 - The Geodetic Set Problem
• UVA - 10048 - Audiophobia
• UVA - 125 - Numbering Paths
• LOJ - Travel Company
• UVA 423 - MPI Maelstrom
• UVA 1416 - Warfare And Logistics
• UVA 1233 - USHER
• UVA 10793 - The Orc Attack
• UVA 10099 The Tourist Guide
• UVA 869 - Airline Comparison
• UVA 13211 - Geonosis
• SPOJ - Defend the Rohan
• Codeforces - Roads in Berland
• Codeforces - String Problem
• GYM - Manic Moving (C)
• SPOJ - Arbitrage
• UVA - 12179 - Randomly-priced Tickets
• LOJ - 1086 - Jogging Trails
• SPOJ - Ingredients
• CSES - Shortest Routes II

Відеоматеріали