Відкрити головне меню

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

Алгоритм Дейкстри
Час виконання алгоритму
Клас Алгоритм пошуку
Структура даних Граф
Найгірша швидкодія

Формулювання задачіРедагувати

Варіант 1. Дана мережа автомобільних доріг, що з'єднують міста Львівської області. Знайти найкоротшу відстань від Львова до кожного міста області, якщо рухатись можна тільки по дорогах.

Варіант 2. Дана карта велосипедних доріжок Латвії та Білорусі. Знайти мінімальну відстань, яку треба проїхати, щоб дістатися від Риги до Бобруйська.

Варіант 3. Є план міста з нанесеними на нього місцями розміщення пожежних частин. Знайти найближчу до кожного дому пожежну станцію.

АбстракціяРедагувати

Дано неорієнтований зв'язний граф G(V, U). Знайти відстань від вершини a до всіх інших вершин V.

Інтуїтивне поясненняРедагувати

Зберігатимемо поточну мінімальну відстань до всіх вершин V (від даної вершини a) і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівними нескінченості, а до вершини а — нулю.   Розглянемо виконання алгоритму на прикладі. Хай потрібно знайти відстані від 1-ї вершини до всіх інших. Кружечками позначені вершини, лініями — шляхи між ними («дуги»). Над дугами позначена їх «ціна» — довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини.

Крок 1Редагувати

Ініціалізація. Відстань до всіх вершин графа V =  . Відстань до а = 0. Жодна вершина графа ще не опрацьована.
 

Крок 2Редагувати

Знаходимо таку вершину (із ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда.
 

Крок 3Редагувати

Перший по порядку сусід 1-ї вершини — 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.
 

Кроки 4, 5Редагувати

Аналогічну операцію проробляємо з двома іншими сусідами 1-ї вершини — 3-ю та 6-ю.
   

Крок 6Редагувати

Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною і обговоренню не підлягає (те, що це дійсно так, вперше довів Дейкстра). Тому викреслимо її з графа, щоб відмітити цей факт.  

Крок 7Редагувати

Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7.   І знову намагаємося зменшити відстань до всіх сусідів 2-ї вершини, намагаючись пройти в них через 2-у. Сусідами 2-ї вершини є 1, 3, 4.

Крок 8Редагувати

Перший (по порядку) сусід вершини № 2 — 1-ша вершина. Але вона вже оброблена (або викреслена — див. крок 6). Тому з 1-ю вершиною нічого не робимо.

Крок 8 (з іншими вхідними даними)Редагувати

Інший сусід вершини 2 — вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ї + відстань між 2-ю і 4-ю вершинами = 7 + 15 = 22. Оскільки 22 < ∞, встановлюємо відстань до вершини № 4 рівним 22.  

Крок 9Редагувати

Ще один сусід вершини 2 — вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини № 3 і дорівнює 9, тому поточну відстань до 3-ї вершини не міняємо.  

Крок 10Редагувати

Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і викреслюємо її з графа.  

Кроки 11 — 15Редагувати

По вже «відпрацьованій» схемі повторюємо кроки 2 — 6. Тепер «найближчою» виявляється вершина № 3. Після її «обробки» отримаємо такі результати:
 

Наступні крокиРедагувати

Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).
     

Завершення виконання алгоритмуРедагувати

Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ї вершини до 2-ї становить 7, до 3-ї — 9, до 4-ї — 20, до 5-ї — 20, до 6-ї — 11 умовних одиниць.

Найпростіша реалізаціяРедагувати

Найпростіша реалізація алгоритму Дейкстри потребує   дій. У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 1 і перевіряємо всі сусідні з нею вершини. Якщо в ній відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то зменшуємо його. Цикл завершується коли позначки всіх вершин стають рівними 1.

Реалізація програми пошук найкоротшого шляху алгоритмом ДейкстриРедагувати

Нижче наведено реалізацію програми мовою програмування С++.

#include "stdafx.h"
#include<iomanip>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define word unsigned int

using namespace std;

int i, j, n, p, xn, xk;

int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];
int min(int n){
	int i, result;
	for(i=0;i<n;i++)
	 if(!(flag[i])) 
		 result=i;
	for(i=0;i<n;i++)
		if((l[result]>l[i])&&(!flag[i])) 
			result=i;
	return result;
}
word minim(word x, word y)
{
	if(x<y)
		return x;
	return y;
}
void main()
{   setlocale(LC_ALL, "ukr");
	cout<<"Введіть кількість точок: ";
	cin>>n;
	for(i=0;i<n;i++)
	for(j=0;j<n;j++) c[i][j]=0;
	for(i=0;i<n;i++)
	for(j=i+1;j<n;j++)
{
	cout<<"Введіть відстань від x"<<i+1<<" до x"<<j+1<<": ";
	cin>>c[i][j];
}
	cout<<" ";
	for(i=0;i<n;i++) cout<<" X"<<i+1;
	cout<<endl<<endl;
	for(i=0;i<n;i++)
		{
		printf("X%d",i+1);
	for(j=0;j<n;j++)
		{
		printf("%6d",c[i][j]);
		c[j][i]=c[i][j];
	}
		printf("\n\n");
}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
	if(c[i][j]==0) c[i][j]=65535; //безкінечність
	cout<<"Введіть початкові точки: ";
	cin>>xn;
	cout<<"Введіть кінцеві точки: ";
	cin>>xk;
		xk--;
		xn--;
	if(xn==xk)
	{
	cout<<"Початкова і кінцева точки збігаються."<<endl;
getch();
return;
	}
	for(i=0;i<n;i++)
		{
		flag[i]=0;
		l[i]=65535;
	}
		l[xn]=0;
		flag[xn]=1;
		p=xn;
		itoa(xn+1,s,10);
	for(i=1;i<=n;i++)
	{
		strcpy(path[i],"X");
		strcat(path[i],s);
	}
	do
		{
	for(i=0;i<n;i++)
	if((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
	{
		if(l[i]>l[p]+c[p][i])
	{
		itoa(i+1,s,10);
		strcpy(path[i+1],path[p+1]);
		strcat(path[i+1],"-X");
		strcat(path[i+1],s);
	}
		l[i]=minim(l[i],l[p]+c[p][i]);
}
		p=min(n);
		flag[p]=1;
	}
	while(p!=xk);
		if(l[p]!=65535)
		{
cout<<"Шлях: "<<path[p+1]<<endl;
cout<<"Довжина шляху: "<<l[p]<<endl;
	}
	else
cout<<"Такого шляху не iснує"<<endl;
getch();
}

В математичних термінахРедагувати

Нехай u — вершина, від якої шукаються відстані, V — множина вершин графа, di — відстань від вершини u до вершини i, , w(i, j) — вага «ребра» (i, j).

Алгоритм:

1. Множина вершин U, до яких відстань відома, встановлюється рівною {u}.

2. Якщо U=V, алгоритм завершено.

3. Потенційні відстані Di до вершин з V\U встановлюються нескінченними.

4. Для всіх ребер (i, j), де i∈U та j∈V\U, якщо Dj>di+w(i, j), то Dj присвоюється di+w(i, j).

5. Шукається i∈V\U, при якому Di мінімальне.

6. Якщо Di дорівнює нескінченності, алгоритм завершено. В іншому випадку di присвоюється значення Di, U присвоюється U∪{i} і виконується перехід до кроку 2.

ПосиланняРедагувати