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

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

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

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

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

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

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

На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 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<<"Такого шляху не існує"<<endl;
    getch();
}

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

Алгоритм:

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

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

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

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

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

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

• Задача комівояжера
• Алгоритм пошуку A*

• Пояслення алгоритму Дейкстри на каналі "Computerphile" на YouTube (англ.)
• algolist.manual.ru
• Опис, код, анімація на сайті університету Окланда (англ.)
• C. Анисимов. Как построить кратчайший маршрут между двумя точками.
• Реализация простейшего варианта алгоритма Дейкстры на e-maxx.ru
• Реализация варианта алгоритма Дейкстры для разреженных графов на e-maxx.ru
• Реализация на основе очереди с приоритетами на C++
• Реализация на основе очереди с приоритетами на Java