Алгоритм голландского ученого Де́йкстры (англ. Dijkstra’s algorithm) находит все кратчайшие пути из одной изначально заданной вершины графа до всех остальных. С его помощью, при наличии всей необходимой информации, можно, например, узнать какую последовательность дорог лучше использовать, чтобы добраться из одного города до каждого из многих других, или в какие страны выгодней экспортировать нефть и тому подобное.
 
 
 

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

Для программной реализации алгоритма понадобиться два массива: логический visited – для хранения информации о посещенных вершинах и численный distance, в который будут заноситься найденные кратчайшие пути. Итак, имеется граф G=(V, E). Каждая из вершин входящих во множество V, изначально отмечена как не посещенная, т. е. элементам массива visited присвоено значение false.

Поскольку самые выгодные пути только предстоит найти, в каждый элемент вектора distance записывается такое число, которое заведомо больше любого потенциального пути (обычно это число называют бесконечностью, но в программе используют, например максимальное значение конкретного типа данных). В качестве исходного пункта выбирается вершина s и ей приписывается нулевой путь: distance[s]=0, т. к. нет ребра из s в s (метод не предусматривает петель).

Далее, находятся все соседние вершины (в которые есть ребро из s) [пусть таковыми будут t и u] и поочередно исследуются, а именно вычисляется стоимость маршрута из s поочередно в каждую из них:

  • distance[t]=distance[s]+вес инцидентного s и t ребра;
  • distance[u]=distance[s]+ вес инцидентного s и u ребра.

Но вполне вероятно, что в ту или иную вершину из s существует несколько путей, поэтому цену пути в такую вершину в массиве distance придется пересматривать, тогда наибольшее (не оптимальное) значение игнорируется, а наименьшее ставиться в соответствие вершине.

После обработки смежных с s вершин она помечается как посещенная: visited[s]=true, и активной становится та вершина, путь из s в которую минимален. Допустим, путь из s в u короче, чем из s в t, следовательно, вершина u становиться активной и выше описанным образом исследуются ее соседи, за исключением вершины s. Далее, u помечается как пройденная: visited[u]=true, активной становится вершина t, и вся процедура повторяется для нее. Алгоритм Дейкстры продолжается до тех пор, пока все доступные из s вершины не будут исследованы.

 

Теперь на конкретном графе проследим работу алгоритма, найдем все кратчайшие пути между истоковой и всеми остальными вершинами. Размер (количество ребер) изображенного ниже графа равен 7 (|E|=7), а порядок (количество вершин) – 6 (|V|=6). Это взвешенный граф, каждому из его ребер поставлено в соответствие некоторое числовое значение, поэтому ценность маршрута необязательно определяется числом ребер, лежащих между парой вершин.

Из всех вершин входящих во множество V выберем одну, ту, от которой необходимо найти кратчайшие пути до остальных доступных вершин. Пусть таковой будет вершина 1. Длина пути до всех вершин, кроме первой, изначально равна бесконечности, а до нее – 0, т. к. граф не имеет петель.

У вершины 1 ровно 3 соседа (вершины 2, 3, 5), и чтобы вычислить длину пути до них нужно сложить вес дуг, лежащих между вершинами: 1 и 2, 1 и 3, 1 и 5 со значением первой вершины (с нулем):

 

2←1+0
3←4+0
5←2+0

 

Как уже отмечалось, получившиеся значения присваиваются вершинам, лишь в том случае если они «лучше» (меньше) тех которые значатся на настоящий момент. А так как каждое из трех чисел меньше бесконечности, они становятся новыми величинами, определяющими длину пути из вершины 1 до вершин 2, 3 и 5.

Далее, активная вершина помечается как посещенная, статус «активной» (красный круг) переходит к одной из ее соседок, а именно к вершине 2, поскольку она ближайшая к ранее активной вершине.

У вершины 2 всего один не рассмотренный сосед (вершина 1 помечена как посещенная), расстояние до которого из нее равно 9, но нам необходимо вычислить длину пути из истоковой вершины, для чего нужно сложить величину приписанную вершине 2 с весом дуги из нее в вершину 4

 

4←1+9

 

Условие «краткости» (10<∞) выполняется, следовательно, вершина 4 получает новое значение длины пути.

Вершина 2 перестает быть активной, также как и вершина 1 удаляется из списка не посещённых. Теперь тем же способом исследуются соседи вершины 5, и вычисляется расстояние до них.

Когда дело доходит до осмотра соседей вершины 3, то тут важно не ошибиться, т. к. вершина 4 уже была исследована и расстояние одного из возможных путей из истока до нее вычислено. Если двигаться в нее через вершину 3, то путь составит 4+7=11, а 11>10, поэтому новое значение игнорируется, старое остается.

Аналогичная ситуация с вершиной 6. Значение самого близкого пути до нее из вершины 1 равно 10, а оно получается только в том случае, если идти через вершину 5.

Когда все вершины графа, либо все те, что доступны из истока, будут помечены как посещенные, тогда работа алгоритма Дейкстры завершится, и все найденные пути будут кратчайшими. Так, например, будет выглядеть список самых оптимальных расстояний лежащих между вершиной 1 и всеми остальными вершинами, рассматриваемого графа:

 

1→1=0
1→2=1
1→3=4
1→4=10
1→5=2
1→6=10

 

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

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <sstream>
#include <stack>

#ifndef _DEPRECATION_DISABLE   /* One time only */
#define _DEPRECATION_DISABLE   /* Disable deprecation true */
#if (_MSC_VER >= 1400)         /* Check version */
#pragma warning(disable: 4996) /* Disable deprecation */
#endif /* #if defined(NMEA_WIN) && (_MSC_VER >= 1400) */
#endif /* #ifndef _DEPRECATION_DISABLE */

using namespace std;

int GR[11111][11111] = { 0, 0 };
int distance1[111111];
int count1, index1, i1, u1;
bool visited1[11111];

void Dijkstra(int st,const int V)
{	
	for (i1 = 1; i1 <= V; i1++)
	{
		distance1[i1] = INT_MAX; visited1[i1] = false;
	}
	distance1[st] = 0;
	queue<int>qii;
	qii.push(st);
	while (!qii.empty()){

		u1 = qii.front();
		qii.pop();
		visited1[u1] = true;
		for (i1 = 1; i1 <= V; i1++){
			if (!visited1[i1] && GR[u1][i1] && distance1[u1] + GR[u1][i1] < distance1[i1]){
				distance1[i1] = distance1[u1] + GR[u1][i1];
				qii.push(i1);
			}
		}
	}
	
}

int main()
{

int n, m;
cin >> n >> m;
	/*
	6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 6 2
3 4 11
4 5 6
5 6 9*/	
	for (int k = 0; k < m; k++){
		int a, b, c;
		cin >> a >> b >> c;
		GR[a][b] = c;
		GR[b][a] = c;
	}

	Dijkstra(1,n);	
	return 0;
}

 

 

 

 

 

Комментарии   

0 # Максим 28.10.2018 16:29
Да, оно за O(E log V).

Его можно немного ускорить (думаю, раза в полтора-два) если отказаться от STL - т.е. написать свою собственную кучу вместо std::queue, и реализовать списки смежности через массивы, а вижу у вас через массивы.
Ответить | Ответить с цитатой | Цитировать