Dijkstra | kz-maxx

Дейкстра алгоритмі деген не?

Дейкстра алгоритмі — бір start вершинадан барлық басқа вершинаға дейінгі ең қысқа расстояние табатын алгоритм.

Бұл алгоритм реброларда вес болған кезде қолданылады. Бірақ барлық вес теріс емес болуы керек.

Егер графта negative edge болса, обычный Дейкстра жарамайды. Ондай кезде Bellman-Ford алгоритмі керек.

Қай жерде қолданылады?

бір вершинадан барлық вершинаға shortest distance табу
екі вершина арасындағы shortest path табу
реброларында вес бар графтарда
карта, жол, маршрут задачаларында
минималды стоимость табу керек болса

Негізгі идея

Біз dist массивін сақтаймыз.

dist[v]

Бұл start вершинадан v вершинасына дейінгі ең қысқа расстояние.

Басында:

dist[start] = 0
dist[қалғандары] = INF

Кейін біз расстояниелерді біртіндеп жақсартамыз.

егер dist[v] + ребро весі < dist[to]
онда жақсырақ путь таптық
dist[to] жаңартамыз

if (dist[v] + w < dist[to]) {
    dist[to] = dist[v] + w;
}

Relaxation деген не?

Relaxation — бір вершинаға дейінгі distance-ты жақсарту әрекеті.

Мысалы:

dist[v] = 5
v → to ребросының весі 3
онда to-ға v арқылы бару: 5 + 3 = 8

Егер бұрын:

dist[to] = 15

Жаңа жол жақсырақ:

8 < 15
dist[to] = 8

Неге priority_queue керек?

Әр қадамда біз ең кіші distance бар вершина алуымыз керек.

Ол үшін C++ ішінде:

priority_queue

Бірақ C++-тағы обычный priority_queue — max-heap. Ал бізге min-heap керек. Сондықтан былай жазамыз:

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

Queue ішіне pair саламыз:

{distance, вершина}

Граф мысалы

Мынадай граф болсын:

1 --5-- 2
1 --2-- 3
3 --1-- 2
2 --3-- 4
3 --7-- 4

Start вершина: 1.

Ең қысқа distance:

Вершина	1-ден distance
1	0
2	3
3	2
4	6

Неге 2-ге distance 3?

1 → 3 → 2
2 + 1 = 3

Неге 4-ке distance 6?

1 → 3 → 2 → 4
2 + 1 + 3 = 6

Граф структурасы

Реброда вес болғандықтан, adjacency list ішінде pair сақтаймыз:

vector<pair<int, int>> g[N];

Мұнда:

first — қай вершинаға барамыз
second — реброның весі

Мысалы, ребро:

1 --5-- 2

Онда былай қосамыз:

g[1].push_back({2, 5});
g[2].push_back({1, 5});

Базалық Дейкстра функциясы

void dijkstra(int start) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                q.push({dist[to], to});
            }
        }
    }
}

if (d != dist[v]) не үшін керек?

priority_queue ішінде ескі информация қалып қоюы мүмкін.

Мысалы, алдымен 2 вершинасына distance 10 таптық. Кейін жақсырақ жол тауып, distance 3 болды.

Queue ішінде болуы мүмкін:
{10, 2}
{3, 2}

Егер біз ескі {10, 2} pair-ды алсақ, ол енді керек емес. Сондықтан оны өткізіп жібереміз.

if (d != dist[v]) {
    continue;
}

Задача 1: бір вершинадан distance

Неориентированный weighted graph берілген. s вершинасынан барлық вершинаға дейінгі shortest distance табу керек.

Input

Output

0 3 2 6

Формат:

n m s
a b w
a b w
...

Толық реализация

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

const int N = 100010;
const long long INF = 4e18;

int n, m, s;
vector<pair<int, int>> g[N];
long long dist[N];

void dijkstra(int start) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                q.push({dist[to], to});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s;

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    dijkstra(s);

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            cout << -1 << ' ';
        } else {
            cout << dist[i] << ' ';
        }
    }

    return 0;
}

Shortest path қалпына келтіру

Егер тек distance емес, жолдың өзін шығару керек болса, p массиві керек.

int p[N];

Біз to вершинасына distance жақсартқанда, қайдан келгенімізді сақтаймыз:

p[to] = v;

Бұл дегеніміз:

to вершинасына v вершинасынан келдік

Path қалай қалпына келеді?

Finish вершинадан бастап parent арқылы артқа жүреміз.

vector<int> path;

for (int v = finish; v != -1; v = p[v]) {
    path.push_back(v);
}

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

Мысалы:

path: 1 → 3 → 2 → 4
p[4] = 2
p[2] = 3
p[3] = 1
p[1] = -1

Задача 2: shortest path шығару

Граф, start s және finish t берілген. s-тен t-ға дейінгі shortest path шығару керек.

Input

Output

1 3 2 4

Path-пен толық реализация

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

const int N = 100010;
const long long INF = 4e18;

int n, m, s, t;
vector<pair<int, int>> g[N];
long long dist[N];
int p[N];

void dijkstra(int start) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        long long d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                p[to] = v;
                q.push({dist[to], to});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        p[i] = -1;
    }

    for (int i = 1; i <= m; i++) {
        int a, b, w;
        cin >> a >> b >> w;

        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    dijkstra(s);

    if (dist[t] == INF) {
        cout << -1;
        return 0;
    }

    vector<int> path;

    for (int v = t; v != -1; v = p[v]) {
        path.push_back(v);
    }

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

    for (int x : path) {
        cout << x << ' ';
    }

    return 0;
}

Ориентированный граф

Егер граф ориентированный болса, ребро тек бір жаққа жүреді.

Ребро:

a → b весі w

Онда тек былай қосамыз:

g[a].push_back({b, w});

Ал мынау керек емес:

g[b].push_back({a, w});

Dijkstra vs BFS

Алгоритм	Граф	Не табады
BFS	невзвешенный	ребро саны бойынша shortest path
Dijkstra	weighted, вес теріс емес	вес суммасы бойынша shortest path

Егер барлық вес 1 болса, BFS қолдануға болады. Егер вес әртүрлі болса, Дейкстра керек.

Дейкстраны қашан қолдануға болмайды?

Егер графта negative weight болса, ordinary Дейкстраны қолдануға болмайды.

1 → 2 вес 5
1 → 3 вес 2
3 → 2 вес -10

Negative edge алгоритм логикасын бұзуы мүмкін.

Negative edges үшін Bellman-Ford қолдан. Барлық жұп вершина үшін Floyd-Warshall қолдануға болады.

Асимптотика

Реализация	Уақыт	Память
priority_queue	O((n + m) log n)	O(n + m)
обычный массив	O(n² + m)	O(n + m)

Олимпиадалық задачаларда көбіне priority_queue арқылы реализация қолданылады.

Қысқа шаблон

const long long INF = 4e18;

vector<pair<int, int>> g[N];
long long dist[N];

void dijkstra(int s) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;

    dist[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        auto cur = q.top();
        q.pop();

        long long d = cur.first;
        int v = cur.second;

        if (d != dist[v]) {
            continue;
        }

        for (auto edge : g[v]) {
            int to = edge.first;
            int w = edge.second;

            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                q.push({dist[to], to});
            }
        }
    }
}