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

C++   20 августа 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). В процессе работы алгоритма Дейкстры поддерживается множество U \subseteq V, состоящие из вершин v орграфа G, для которых кратчайшее расстояние dist[v] уже найдено. Булевский массив used служит для реализации множества U \subseteq V и хранения информации о том, найдено ли кратчайшее расстояние от стартовой вершины start до вершины v или еще нет. Массив pred служит для хранения предков и необходим для восстановления кратчайших путей из стартовой вершины start до всех остальных вершин v \in V орграфа G = (V, E).


vector *adj; //список смежности
vector *weight; //вес ребра в орграфе
vector used; //массив для хранения информации о пройденных и не пройденных вершинах
int *dist; //массив для хранения расстояния от стартовой вершины
int *pred; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины

В качестве списка смежности для представления графа на языке C++ удобно использовать массив, каждый элемент которого является структурой данных vector<int>.
В приведенной ниже реализации данные считываются и выводятся в консоль.

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

В первой строке входного файла задано два целых числа: 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 является пустой.


#include
#include
#include
#include

using namespace std;

static int INF = INT_MAX / 2;

int n; //количество вершин в орграфе
int m; //количество дуг в орграфе
vector *adj; //список смежности
vector *weight; //вес ребра в орграфе
vector used; //массив для хранения информации о пройденных и не пройденных вершинах
int *dist; //массив для хранения расстояния от стартовой вершины
int *pred; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
int start; //стартовая вершина, от которой ищется расстояние до всех других

//процедура запуска алгоритма Дейкстры из стартовой вершины
void dejkstra(int s) {
dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0
for (int iter = 0; iter < n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины 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]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли void readData(){ scanf("%d %d %d", &n, &m, &start); //считываем количество вершин, количество дуг графа и стартовую вершину start--; //инициализируем списка смежности графа размерности n adj = new vector[n];
//инициализация списка, в котором хранятся веса ребер
weight = new vector[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(); dejkstra(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++