Алгоритм Дейкстры для разреженных графов (реализация на C++)

C++   29 Август 2015  Автор статьи:  

Задан ориентированный взвешенный граф G = (V, E), состоящий из N вершин и M дуг. Каждая дуга (u, v) имеет неотрицательный вес w(u, v), w(u, v) \ge 0. Требуется найти кратчайшие пути из некоторой стартовой вершины s до всех остальных вершин графа G.
Исходный граф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Для хранения весов дуг, соответствующих их положению в списке смежности adj, используется список смежности weight. Переменная start обозначает стартовую вершину, от которой ищется расстояние до всех других вершин v \in V. Массив dist используется для хранения текущего кратчайшего расстояния от стартовой вершины start до всех других вершин v \in V. Изначально полагаем, что dist[start] = 0, а для всех остальных вершин значение массива dist равно бесконечности INF. На практике при реализации алгоритмов в качестве бесконечности INF выбирают достаточное большое число, заведомо превосходящее длину любого пути в исходном орграфе G = (V, E). Массив pred служит для хранения предков и необходим для восстановления кратчайших путей из стартовой вершины start до всех остальных вершин v \in V орграфа G = (V, E).

1
2
3
4
vector<int> *adj; //список смежности
vector<bool> used; //массив для хранения информации о пройденных и не пройденных вершинах
int mtSize = 0; //размер максимального паросочетания
vector<int> mt; //массив для хранения максимального паросочетания

В качестве списка смежности для представления графа на языке C++ удобно использовать массив, каждый элемент которого является структурой данных vector<int>. Для реализации очереди с приоритетами, в которую попадают вершины в порядке приближенности к стартовой вершине start, используется структура данных set<pair<int, int>>. Пара двух целых чисел pair<int, int> хранит значения weight и v, где weight – текущее расстояние от стартовой вершины start до вершины v, а v – номер вершины в орграфе G соответственно. Для того, чтобы в множестве set<pair<int, int>> вершины автоматически упорядочивались в порядке неубывания расстояния от стартовой вершины start, первым элементом в паре set<pair<int, int>> является расстояние weight, а вторым – v, то есть номер вершины в орграфе G.
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: N (1 \le N \le 10^5) – количество вершин в графе, M (1 \le M \le 10^6) – количество ребер графа соответственно и стартовая вершина start (1 \le start \le N). Каждая из следующих M строк содержит описание дуги орграфа: три целых числа – начало, конец и вес дуги. Начало и конец дуги находятся в диапазоне от 1 до N, а вес ребра – это целое не отрицательно число.

Выходные данные

В первой строке выходного файла показано расстояние из стартовой вершины start до всех остальных вершин v \in V орграфа G = (V, E) в порядке их нумерации. Если пути из стартовой вершины start до некоторой вершины не существует, то на том месте стоит значение -1.
Далее в следующий N строках показан номер вершины и кратчайший путь до нее из стартовой вершины start. В случае, если пути до некоторой вершины v \in V не существует, то строка с номером v является пустой.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

static int INF = INT_MAX / 2;
   
int n; //количество вершин в орграфе
int m; //количествое дуг в орграфе
vector<int> *adj; //список смежности
vector<int> *weight; //вес ребра в орграфе
vector<bool> used; //массив для хранения информации о пройденных и не пройденных вершинах
int *dist; //массив для хранения расстояния от стартовой вершины
int *pred; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
int start; //стартовая вершина, от которой ищется расстояние до всех других
set<pair<int, int>> queue; //очередь с приоритетами
   
//процедура запуска алгоритма Дейкстры из стартовой вершины
void sparseDejkstra(int s) {
    dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0
    queue.insert(make_pair(dist[s], s));
    while (!queue.empty()) {
        //извлекаем вершину, которая находится вверху кучи
        int v = queue.begin()->second;
        int distV = queue.begin()->first;
        queue.erase(queue.begin());
        //рассматриваем все дуги, исходящие из вершины вверху кучи
        for (int i = 0; i < adj[v].size(); ++i) {
            int u = adj[v][i];
            int weightU = weight[v][i];
            //релаксация вершины
            if (dist[v] + weightU < dist[u]) {
                queue.erase(make_pair(dist[u], u));
                dist[u] = dist[v] + weightU;
                pred[u] = v;
                queue.insert(make_pair(dist[u], u));
            }
        }
    }
}
   
//процедура считывания входных данных с консоли
void readData(){
    scanf("%d %d %d", &n, &m, &start); //считываем количество вершин, количество дуг графа и стартовую вершину
    start--;
       
    //инициализируем списка смежности графа размерности n
    adj = new vector<int>[n];
    //инициализация списка, в котором хранятся веса ребер
    weight = new vector<int>[n];
       
    //считываем граф, заданный списком ребер
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        u--;
        v--;
        adj[u].push_back(v);
        weight[u].push_back(w);
    }
       
    used.resize(n, false);
   
    pred = new int[n];
    dist = new int[n];
    for (int i = 0; i < n; ++i) {
        pred[i] = -1;
        dist[i] = INF;
    }
       
}
   
//процедура восстановления кратчайшего пути по массиву предком
void printWay(int v) {
    if (v == -1) {
        return;
    }
    printWay(pred[v]);
    printf("%d ", (v + 1));
}
   
//процедура вывода данных в консоль
 void printData() {
    for (int v = 0; v < n; ++v) {
        if (dist[v] != INF) {
            printf("%d ", dist[v]);
        } else {
            printf("-1 ");
        }
    }
    printf("\n");
    for (int v = 0; v < n; ++v) {
        printf("%d: ", (v + 1));
        if (dist[v] != INF) {
            printWay(v);
        }
        printf("\n");
    }
}
   
 void run() {
    readData();
    sparseDejkstra(start);
    printData();
}  

int main()
{
    run();
    return 0;
}

 

Пример
Входные данные
7 11 1
1 2 1
1 3 7
2 4 4
2 5 2
3 2 4
3 5 5
4 5 3
5 3 3
5 4 10
6 7 3
7 6 4
Выходные данные
0 1 6 5 3 -1 -1
1: 1
2: 1 2
3: 1 2 5 3
4: 1 2 4
5: 1 2 5
6:
7:

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++