Алгоритм Дейкстри

Нам задано орієнтований або неорієнтований зважений граф з $n$ вершинами та $m$ ребрами. Ваги всіх ребер невід'ємні. Також задано початкову вершину $s$. У цій статті ми розглянемо, як знайти довжини найкоротших шляхів від початкової вершини $s$ до всіх інших вершин, а також вивести самі найкоротші шляхи.

Цю задачу також називають задачею про найкоротші шляхи з однієї вершини (single-source shortest paths problem).

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

• Усі ваги ребер невід'ємні? (якщо є від'ємні ребра → Беллман-Форд)
• Потрібні найкоротші шляхи з однієї вершини, а не між усіма парами? (якщо потрібні всі пари при малому $V$ → Флойд-Воршелл)
• Ваги довільні (не лише $\{0,1\}$)? (якщо ваги лише $0$ та $1$ → швидший 0-1 BFS; якщо граф незважений → BFS)
• Граф щільний? Ця реалізація за $O(n^2)$ оптимальна для щільних графів; (для розріджених графів → версія з купою/set)

Алгоритм

Ось алгоритм, описаний нідерландським комп'ютерним науковцем Едсгером В. Дейкстрою у 1959 році.

Створимо масив $d[]$, у якому для кожної вершини $v$ зберігатимемо поточну довжину найкоротшого шляху від $s$ до $v$ у $d[v]$. Спочатку $d[s] = 0$, а для всіх інших вершин ця довжина дорівнює нескінченності. У реалізації за нескінченність обирають достатньо велике число (яке гарантовано більше за будь-яку можливу довжину шляху).

$$d[v] = \infty,~ v \ne s$$

Окрім того, ми підтримуємо булів масив $u[]$, у якому для кожної вершини $v$ зберігається, чи вона позначена. Спочатку всі вершини непозначені:

$$u[v] = {\rm false}$$

Алгоритм Дейкстри виконується протягом $n$ ітерацій. На кожній ітерації як вершина $v$ обирається непозначена вершина, що має найменше значення $d[v]$:

Очевидно, що на першій ітерації буде обрано початкову вершину $s$.

Обрана вершина $v$ позначається. Далі з вершини $v$ виконуються релаксації: розглядаються всі ребра виду $(v,\text{to})$, і для кожної вершини $\text{to}$ алгоритм намагається покращити значення $d[\text{to}]$. Якщо довжина поточного ребра дорівнює $len$, то код релаксації має вигляд:

$$d[\text{to}] = \min (d[\text{to}], d[v] + len)$$

Після того як усі такі ребра розглянуто, поточна ітерація завершується. Нарешті, після $n$ ітерацій усі вершини будуть позначені, і алгоритм завершується. Ми стверджуємо, що знайдені значення $d[v]$ є довжинами найкоротших шляхів від $s$ до всіх вершин $v$.

Зауважимо, що якщо деякі вершини недосяжні з початкової вершини $s$, то значення $d[v]$ для них залишаться нескінченними. Очевидно, що на кількох останніх ітераціях алгоритм обиратиме саме ці вершини, але жодної корисної роботи для них зроблено не буде. Тому алгоритм можна зупинити, щойно обрана вершина має нескінченну відстань до неї.

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

Зазвичай потрібно знати не лише довжини найкоротших шляхів, а й самі найкоротші шляхи. Подивимося, як підтримувати достатньо інформації, щоб відновити найкоротший шлях від $s$ до будь-якої вершини. Ми підтримуватимемо масив попередників $p[]$, у якому для кожної вершини $v \ne s$ значення $p[v]$ — це передостання вершина в найкоротшому шляху від $s$ до $v$. Тут ми використовуємо той факт, що якщо взяти найкоротший шлях до деякої вершини $v$ і прибрати з цього шляху $v$, то отримаємо шлях, що закінчується у вершині $p[v]$, і цей шлях буде найкоротшим для вершини $p[v]$. Цей масив попередників можна використати для відновлення найкоротшого шляху до будь-якої вершини: починаючи з $v$, ми повторно беремо попередника поточної вершини, доки не дійдемо до початкової вершини $s$, і отримуємо потрібний найкоротший шлях із вершинами, перерахованими у зворотному порядку. Отже, найкоротший шлях $P$ до вершини $v$ дорівнює:

$$P = (s, \ldots, p[p[p[v]]], p[p[v]], p[v], v)$$

Побудувати цей масив попередників дуже просто: при кожній успішній релаксації, тобто коли для деякої обраної вершини $v$ відбувається покращення відстані до деякої вершини $\text{to}$, ми оновлюємо вершину-попередника для $\text{to}$ вершиною $v$:

$$p[\text{to}] = v$$

Доведення

Основне твердження, на якому ґрунтується коректність алгоритму Дейкстри, таке:

Після того як будь-яка вершина $v$ стає позначеною, поточна відстань до неї $d[v]$ є найкоротшою і більше не змінюватиметься.

Доведення проводиться методом індукції. Для першої ітерації це твердження очевидне: єдина позначена вершина — це $s$, і відстань до неї $d[s] = 0$ справді є довжиною найкоротшого шляху до $s$. Тепер припустимо, що це твердження істинне для всіх попередніх ітерацій, тобто для всіх уже позначених вершин; доведемо, що воно не порушується після завершення поточної ітерації. Нехай $v$ — вершина, обрана на поточній ітерації, тобто $v$ — це вершина, яку алгоритм позначить. Тепер нам треба довести, що $d[v]$ справді дорівнює довжині найкоротшого шляху до неї $l[v]$.

Розглянемо найкоротший шлях $P$ до вершини $v$. Цей шлях можна розбити на дві частини: $P_1$, яка складається лише з позначених вершин (принаймні початкова вершина $s$ є частиною $P_1$), і решту шляху $P_2$ (вона може містити позначену вершину, але завжди починається з непозначеної вершини). Позначимо першу вершину шляху $P_2$ як $p$, а останню вершину шляху $P_1$ як $q$.

Спочатку доведемо наше твердження для вершини $p$, тобто доведемо, що $d[p] = l[p]$. Це майже очевидно: на одній з попередніх ітерацій ми обрали вершину $q$ і виконали з неї релаксацію. Оскільки (через вибір вершини $p$) найкоротший шлях до $p$ — це найкоротший шлях до $q$ плюс ребро $(p,q)$, релаксація з $q$ встановила значення $d[p]$ рівним довжині найкоротшого шляху $l[p]$.

Оскільки ваги ребер невід'ємні, довжина найкоротшого шляху $l[p]$ (яку ми щойно довели рівною $d[p]$) не перевищує довжину $l[v]$ найкоротшого шляху до вершини $v$. З огляду на те, що $l[v] \le d[v]$ (бо алгоритм Дейкстри не міг знайти коротшого шляху, ніж найкоротший можливий), отримуємо нерівність:

$$d[p] = l[p] \le l[v] \le d[v]$$

З іншого боку, оскільки обидві вершини $p$ і $v$ непозначені, і на поточній ітерації було обрано вершину $v$, а не $p$, отримуємо ще одну нерівність:

$$d[p] \ge d[v]$$

З цих двох нерівностей робимо висновок, що $d[p] = d[v]$, а тоді з раніше знайдених рівностей отримуємо:

$$d[v] = l[v]$$

Що й треба було довести.

Реалізація

Алгоритм Дейкстри виконує $n$ ітерацій. На кожній ітерації він обирає непозначену вершину $v$ з найменшим значенням $d[v]$, позначає її та перевіряє всі ребра $(v, \text{to})$, намагаючись покращити значення $d[\text{to}]$.

Час роботи алгоритму складається з:

• $n$ пошуків вершини з найменшим значенням $d[v]$ серед $O(n)$ непозначених вершин
• $m$ спроб релаксації

Для найпростішої реалізації цих операцій на кожній ітерації пошук вершини потребує $O(n)$ операцій, а кожну релаксацію можна виконати за $O(1)$. Отже, підсумкова асимптотика алгоритму:

$$O(n^2+m)$$

Ця складність оптимальна для щільного графа, тобто коли $m \approx n^2$. Однак у розріджених графах, коли $m$ значно менше за максимальну кількість ребер $n^2$, задачу можна розв'язати зі складністю $O(n \log n + m)$. Алгоритм і реалізацію можна знайти у статті Алгоритм Дейкстри на розріджених графах.

C++

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }
        
        if (d[v] == INF)
            break;
        
        u[v] = true;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;
            
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}

Python

INF = 1000000000

# adj — список суміжності: adj[v] містить пари (to, len)
def dijkstra(s: int, adj: list[list[tuple[int, int]]]) -> tuple[list[int], list[int]]:
    n = len(adj)
    d = [INF] * n              # відстані від s
    p = [-1] * n               # попередники
    u = [False] * n            # позначені вершини

    d[s] = 0
    for _ in range(n):
        # обираємо непозначену вершину з найменшою відстанню
        v = -1
        for j in range(n):
            if not u[j] and (v == -1 or d[j] < d[v]):
                v = j

        if d[v] == INF:
            break

        u[v] = True
        for to, length in adj[v]:
            # релаксація ребра (v, to)
            if d[v] + length < d[to]:
                d[to] = d[v] + length
                p[to] = v

    return d, p

TypeScript

const INF = 1000000000;

// adj — список суміжності: adj[v] містить пари [to, len]
function dijkstra(
    s: number,
    adj: [number, number][][],
): { d: number[]; p: number[] } {
    const n = adj.length;
    const d: number[] = new Array(n).fill(INF); // відстані від s
    const p: number[] = new Array(n).fill(-1);  // попередники
    const u: boolean[] = new Array(n).fill(false); // позначені вершини

    d[s] = 0;
    for (let i = 0; i < n; i++) {
        // обираємо непозначену вершину з найменшою відстанню
        let v = -1;
        for (let j = 0; j < n; j++) {
            if (!u[j] && (v === -1 || d[j] < d[v])) {
                v = j;
            }
        }

        if (d[v] === INF) {
            break;
        }

        u[v] = true;
        for (const [to, len] of adj[v]) {
            // релаксація ребра (v, to)
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }

    return { d, p };
}

Go

const INF = 1000000000

// adj — список суміжності: adj[v] містить пари {to, len}
func dijkstra(s int, adj [][][2]int) (d, p []int) {
    n := len(adj)
    d = make([]int, n) // відстані від s
    p = make([]int, n) // попередники
    u := make([]bool, n) // позначені вершини
    for i := range d {
        d[i] = INF
        p[i] = -1
    }

    d[s] = 0
    for i := 0; i < n; i++ {
        // обираємо непозначену вершину з найменшою відстанню
        v := -1
        for j := 0; j < n; j++ {
            if !u[j] && (v == -1 || d[j] < d[v]) {
                v = j
            }
        }

        if d[v] == INF {
            break
        }

        u[v] = true
        for _, edge := range adj[v] {
            to, length := edge[0], edge[1]
            // релаксація ребра (v, to)
            if d[v]+length < d[to] {
                d[to] = d[v] + length
                p[to] = v
            }
        }
    }

    return d, p
}

Тут граф $\text{adj}$ зберігається як список суміжності: для кожної вершини $v$ значення $\text{adj}[v]$ містить список ребер, що виходять з цієї вершини, тобто список pair<int,int>, де перший елемент пари — це вершина на іншому кінці ребра, а другий елемент — вага ребра.

Функція приймає початкову вершину $s$ і два вектори, які будуть використані як значення, що повертаються.

Найперше код ініціалізує масиви: відстаней $d[]$, позначок $u[]$ і попередників $p[]$. Потім він виконує $n$ ітерацій. На кожній ітерації обирається вершина $v$, яка має найменшу відстань $d[v]$ серед усіх непозначених вершин. Якщо відстань до обраної вершини $v$ дорівнює нескінченності, алгоритм зупиняється. Інакше вершина позначається, і перевіряються всі ребра, що виходять з цієї вершини. Якщо релаксація вздовж ребра можлива (тобто відстань $d[\text{to}]$ можна покращити), то відстань $d[\text{to}]$ і попередник $p[\text{to}]$ оновлюються.

Після виконання всіх ітерацій масив $d[]$ зберігає довжини найкоротших шляхів до всіх вершин, а масив $p[]$ зберігає попередників усіх вершин (крім початкової вершини $s$). Шлях до будь-якої вершини $t$ можна відновити так:

C++

vector<int> restore_path(int s, int t, vector<int> const& p) {
    vector<int> path;

    for (int v = t; v != s; v = p[v])
        path.push_back(v);
    path.push_back(s);

    reverse(path.begin(), path.end());
    return path;
}

Python

def restore_path(s: int, t: int, p: list[int]) -> list[int]:
    path = []

    # йдемо від t назад по попередниках, доки не дійдемо до s
    v = t
    while v != s:
        path.append(v)
        v = p[v]
    path.append(s)

    path.reverse()  # розвертаємо, щоб шлях ішов від s до t
    return path

TypeScript

function restorePath(s: number, t: number, p: number[]): number[] {
    const path: number[] = [];

    // йдемо від t назад по попередниках, доки не дійдемо до s
    for (let v = t; v !== s; v = p[v]) {
        path.push(v);
    }
    path.push(s);

    path.reverse(); // розвертаємо, щоб шлях ішов від s до t
    return path;
}

Go

func restorePath(s, t int, p []int) []int {
    path := []int{}

    // йдемо від t назад по попередниках, доки не дійдемо до s
    for v := t; v != s; v = p[v] {
        path = append(path, v)
    }
    path = append(path, s)

    // розвертаємо, щоб шлях ішов від s до t
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    return path
}

Джерела

• Edsger Dijkstra. A note on two problems in connexion with graphs [1959]
• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005]

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

• Timus - Ivan's Car [Difficulty:Medium]
• Timus - Sightseeing Trip
• SPOJ - SHPATH [Difficulty:Easy]
• Codeforces - Dijkstra? [Difficulty:Easy]
• Codeforces - Shortest Path
• Codeforces - Jzzhu and Cities
• Codeforces - The Classic Problem
• Codeforces - President and Roads
• Codeforces - Complete The Graph
• TopCoder - SkiResorts
• TopCoder - MaliciousPath
• SPOJ - Ada and Trip
• LA - 3850 - Here We Go(relians) Again
• GYM - Destination Unknown (D)
• UVA 12950 - Even Obsession
• GYM - Journey to Grece (A)
• UVA 13030 - Brain Fry
• UVA 1027 - Toll
• UVA 11377 - Airport Setup
• Codeforces - Dynamic Shortest Path
• UVA 11813 - Shopping
• UVA 11833 - Route Change
• SPOJ - Easy Dijkstra Problem
• LA - 2819 - Cave Raider
• UVA 12144 - Almost Shortest Path
• UVA 12047 - Highest Paid Toll
• UVA 11514 - Batman
• Codeforces - Team Rocket Rises Again
• UVA - 11338 - Minefield
• UVA 11374 - Airport Express
• UVA 11097 - Poor My Problem
• UVA 13172 - The music teacher
• Codeforces - Dirty Arkady's Kitchen
• SPOJ - Delivery Route
• SPOJ - Costly Chess
• CSES - Shortest Routes 1
• CSES - Flight Discount
• CSES - Flight Routes

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