Взвешенные графы

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

Взвешенный граф

Типичная задача для таких графов - поиск кратчайшего пути. Например, в этом графе кратчайший путь между вершинами и : , так как его вес равен , а вес ребра равен .

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

Классический алгоритм для поиска кратчайших путей во взвешенном графе - алгоритм Дейкстры (по имени автора Эдгара Дейкстры). Он позволяет найти кратчайший путь от одной вершины графа до всех остальных за ( - количество вершин и рёбер соответственно).

Принцип работы алгоритма напоминает принцип работы BFS: на каждом шаге обрабатывается ближайшая ещё не обработанная вершина (расстояние до неё уже известно). При её обработке все ещё не посещённые соседи добавляются в очередь для посещения (расстояние до каждой из них рассчитывается как расстояние до текущей вершины + длина ребра). Главное отличие от BFS заключается в том, что вместо классической очереди используется очередь с приоритетом. Она позволяет нам выбирать ближайшую вершину за .

Анимация выполнения алгоритма Дейкстры для поиска кратчайшего пути из вершины в вершину :

Анимация алгоритма Дейкстры

С помощью псевдокода алгоритм Дейкстры описывается следующим образом:

ans = массив расстояний от начальной вершины до каждой.
      изначально заполнен бесконечностями (ещё не достигнута).

ans[start] = 0

q = очередь с приоритетом, хранящая пары (v, dst),
    где dst - предполагаемое расстояние до v

добавить (start, 0) в q

пока q не пуста:
    (v, dst) = первая вершина в очереди (с минимальным расстоянием), и расстояние до неё
    извлечь (v, dst) из очереди

    если ans[v] < dst:   //мы уже обработали эту вершину, используя другой путь
        перейти к следующей вершине

    для каждой v -> u:
        n_dst = dst + len(v -> u)   //расстояние до u при прохождении через v
        если n_dst < ans[u]:        //если мы можем улучшить ответ
            ans[u] = n_dst
            добавить (u, n_dst) в q

Как видите, в очереди с приоритетом хранится не только номер вершины, но и вычисленное расстояние до неё, по которому и ведётся сортировка. Также возможна ситуация, при которой одна и та же вершина будет помещена в очередь несколько раз с разным расстоянием (так как она достижима по нескольким рёбрам). В такой ситуации обрабатываем её только один раз (с минимальным возможным расстоянием).

Реализация

В нашей очереди с приоритетом должны храниться пары (вершина, расстояние до неё), причём отсортированы они должны быть по уменьшению расстояния. Для этого нужно использовать тип std::priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>: первым элементом пары будет расстояние, а вторым - номер вершины.

Для хранения взвешенного графа в виде списка смежности для каждой вершины мы храним вектор пар (соседняя вершина, длина ребра до неё).

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;

vector<pair<int, int>> graph[100000];
int ans[100000];

int main() {
    //Ввод графа и вершины start.

    for (int i = 0; i < n; i++) {
        ans[i] = INF;
    }

    ans[start] = 0;

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

    q.push({0, start});

    while (!q.empty()) {
        pair<int, int> c = q.top();
        q.pop();

        int dst = c.first, v = c.second;

        if (ans[v] < dst) {
            continue;
        }

        for (pair<int, int> e: graph[v]) {
            int u = e.first, len_vu = e.second;

            int n_dst = dst + len_vu;
            if (n_dst < ans[u]) {
                ans[u] = n_dst;
                q.push({n_dst, u});
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << "Shortest path from " << start + 1 << " to " << i + 1 << " has length " << ans[i] << endl;
    }
}

Реализация с восстановлением пути

Восстановление пути для алгоритма Дейкстры реализуется точно так же, как и для BFS: при успешном улучшении пути в вершину через вершину , мы запоминаем, что . После окончания работы алгоритма используем массив для восстановления пути в обратном направлении.

Реализация на C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;

vector<pair<int, int>> graph[100000];
int ans[100000];
int pr[100000];     //prev

int main() {
    //Ввод графа и вершин start и end.

    for (int i = 0; i < n; i++) {
        ans[i] = INF;
        pr[i] = -1;   //Значение, обозначающее что из этой вершины возвращаться некуда
    }

    ans[start] = 0;

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

    q.push({0, start});

    while (!q.empty()) {
        pair<int, int> c = q.top();
        q.pop();

        int dst = c.first, v = c.second;

        if (ans[v] < dst) {
            continue;
        }

        for (pair<int, int> e: graph[v]) {
            int u = e.first, len_vu = e.second;

            int n_dst = dst + len_vu;
            if (n_dst < ans[u]) {
                ans[u] = n_dst;
                pr[u] = v;
                q.push({n_dst, u});
            }
        }
    }

    vector<int> path;

    int cur = end;
    path.push_back(cur);

    while (pr[cur] != -1) {
        cur = pr[cur];
        path.push_back(cur);
    }

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

    cout << "Shortest path between vertices " << start + 1 << " and " << end + 1 << " is: " << endl;

    for (int v: path) {
        cout << v + 1 << ", ";
    }
}

Область применения алгоритма Дейкстры

Алгоритм Дейкстры является оптимальным для поиска пути практически в любых графах, но он имеет одно ограничение. Алгоритм Дейкстры неприменим для графов, содержащих рёбра с отрицательным весом. Для поиска кратчайшего пути в таких графах обычно используют алгоритм Форда-Беллмана.