Жадібність в роботі: як влаштований алгоритм Dijkstra

Алгоритм нідерландського вченого Едсгера Дейкстри знаходить найкоротші шляхи від однієї вершини графа до всіх інших у зваженому графі з невід'ємними вагами. Саме на ньому працює більшість навігаційних систем: граф — це дорожня мережа, ваги — відстані або час у дорозі, стартова вершина — ваше поточне місцезнаходження. Задача зводиться до пошуку оптимального маршруту, і Дейкстра вирішує її ефективно. Dijkstra не працює коректно з графами, що містять ребра з від'ємними вагами, тому для таких задач потрібен Bellman-Ford алгоритм. Алгоритм Дейкстри належить до класу жадібних алгоритмів. Що це означає на практиці і чому жадібна стратегія математично виправдана — розбираємо нижче.

Що таке жадібний алгоритм

Жадібний алгоритм (greedy algorithm) — це підхід, за якого на кожному кроці обирається локально оптимальне рішення без перегляду попередніх кроків і без прорахунку майбутніх. Рух лише вперед.

Це радикально відрізняється від динамічного програмування (DP), де рішення будується знизу вгору: спочатку розв'язуються підзадачі, їх результати зберігаються і комбінуються для отримання фінальної відповіді. DP враховує всю історію обчислень, а greedy algorithms лише поточний стан.

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

Як працює Dijkstra 

Алгоритм Дейкстри шукає найкоротші шляхи від стартової вершини до всіх інших у зваженому графі з невід'ємними вагами. На кожній ітерації відбувається наступне:

1. Серед ще не оброблених вершин обирається та, що має мінімальну відому відстань.

2. Ця відстань фіналізується — повторного перегляду не буде.

3. Відстані до сусідів оновлюються через релаксацію.

Ключовий момент — крок 2. Це і є жадібне рішення: відстань визнається фінальною одразу, без перебору альтернатив.

Чому це коректно? Тому що всі ваги невід'ємні. Якщо вершина має мінімальну відому відстань d, будь-який інший шлях до неї проходить через вершини з відстанями ≥ d і додає невід'ємні ребра. Жоден альтернативний маршрут не дасть менше d. Це і є математичне обґрунтування жадібного вибору.

Саме тут проходить межа з Bellman-Ford: там відстані не фіналізуються жадібно, а перераховуються V−1 разів для всіх ребер — підхід, ближчий до DP. Це дозволяє коректно працювати з від'ємними вагами, але коштує складністю O(V × E) замість O((V + E) log V).

Реалізація на C++

Реалізація використовує priority_queue зі стандартної бібліотеки C++ — структуру даних, яка автоматично тримає елемент з найменшим значенням на вершині. Це дозволяє щоразу діставати вершину з мінімальною відомою відстанню без лінійного перебору всіх варіантів.

#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX;

vector<int> dijkstra(int src, int V, vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(V, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [weight, v] : adj[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

adj[u] — список пар {weight, v} для кожного ребра з вершини u. priority_queue з greater<> налаштовує чергу так, що елемент з найменшим значенням завжди знаходиться на вершині — саме те, що потрібно для вибору вершини з мінімальною відстанню на кожній ітерації.

Рядок if (d > dist[u]) continue реалізує lazy deletion: якщо вершина вже оброблена з кращою відстанню, застарілий запис у черзі пропускається. Це стандартна оптимізація замість явного видалення елемента з черги.

Часова складність: O((V + E) log V). Кожне ребро обробляється один раз, кожна операція з чергою — O(log V).

Де застосовують алгоритм Dijkstra 

Навігація і картографія. Google Maps та більшість навігаційних систем використовують варіації алгоритму Dijkstra; алгоритм A* — це Dijkstra з евристичною функцією, яка пришвидшує пошук у напрямку цілі.

Мережева маршрутизація. OSPF (Open Shortest Path First) — link-state протокол, що будує дерево найкоротших шляхів на кожному маршрутизаторі на основі Dijkstra.

Ігровий pathfinding. A* у більшості ігрових рушіїв — це той самий жадібний підхід з доданою евристикою для обмеження простору пошуку.

Dijkstra — приклад того, як жадібна стратегія дає глобально оптимальний результат за чітко визначених умов. Прибрати невід'ємність ваг — і коректність розсипається. Саме тому розуміти обмеження алгоритму важливіше, ніж знати його реалізацію напам'ять.

Детальніше Dijkstra і greedy алгоритми розбираються в модулі Graphs and Trees курсу Algorithms in Practice.