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

Одним з варіантів вирішення ЗК є варіант знаходження найкоротшої ланцюга, що містить всі міста. Потім отримана ланцюг доповнюється початковим містом - виходить шуканий тур.

Можна запропонувати багато процедур вирішення цього завдання, наприклад, фізичне моделювання. На плоскій дошці малюється карта місцевості, в міста, що лежать на розвилці доріг, забиваються цвяхи, на кожен цвях надівається кільце, дороги укладаються мотузками, які прив'язуються до відповідних кілець. Щоб знайти найкоротша відстань між i і k, потрібно взяти I в одну руку і k в іншу і розтягнути. Ті мотузки, які натягнуться і не дадуть розводити руки ширше і утворюють найкоротший шлях між i і k. Проте математична процедура, яка Промоделюйте цю фізичну, виглядає дуже складно. Відомі алгоритми простіше. Один з них - алгоритм Дейкстри, запропонований Дейкстрой ще в 1959р. Цей алгоритм вирішує загальну задачу:

В орієнтованої, неориентированной або змішаної (т. Е. Такий, де частина доріг має односторонній рух) мережі знайти найкоротший шлях між двома заданими вершинами.

Алгоритм використовує три масиву з n (= числу вершин мережі) чисел кожен. Перший масив a містить мітки з двома значеннями: 0 (вершина ще не розглянута) та 1 (вершина вже розглянута); другий масив b містить відстані - поточні найкоротші відстані від vi до відповідної вершини; третій масив c містить номери вершин - k-й елемент ck є номер передостанній вершини на поточному найкоротшому шляху з vi в vk. Матриця відстаней Dik задає довжини дуг dik; якщо такий дуги немає, то dik присвоюється велика кількість Б, рівне «машинної нескінченності».

Тепер можна описати:

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

1 (ініціалізація).

У циклі від одного до n заповнити нулями масив а; заповнити числом i масив з: перенести i-тую рядок матриці D в масив b;

a [i]: = 1; c [i]: = 0; {i-номер стартовою вершини}

2 (загальний крок).

Знайти мінімум серед невідмічених (т. Е. Тих k, для яких a [k] = 0); нехай мінімум досягається на індексі j, т. е. bjbk; a [j]: = 1;

0	23	12	∞	∞	∞	∞	∞
23	0	25	∞	22	∞	∞	35
12	25	0	18	∞	∞	∞	∞
∞	∞	18	0	∞	20	∞	∞
∞	22	∞	∞	0	23	14	∞
∞	∞	∞	20	23	0	24	∞
∞	∞	∞	∞	14	24	0	16
∞	35	∞	∞	∞	∞	16	0
табл. 12

якщо bk> bj + djk то (bk: = bj + djk; ck: = j) {Умова означає, що шлях vi..vk довший, ніж шлях vi..vj, vk. Якщо все a [k] відзначені, то довжина шляху vi..vk дорівнює b [k]. Тепер треба перерахувати вершини, що входять до найкоротший шлях}

3 (видача відповіді).

{Шлях vi..vk видається в зворотному порядку наступною процедурою:}

3.1. z: = c [k];

3.2. Видати z;

3.3. z: = c [z]; Якщо z = 0, то кінець, інакше перейти до 3.2.

Д ля виконання алгоритму потрібно n раз переглянути масив b з n елементів, т. Е. Алгоритм Дейкстри має квадратичну складність. Проілюструємо роботу алгоритму Дейкстри чисельним прикладом (для більшої складності, вважаємо, що деякі міста (вершини) i, j пов'язані між собою, т. Е. D [i, j] = ∞). Нехай, наприклад, i = 3. Потрібно знайти найкоротші шляхи з вершини 3. Вміст масивів a, b, c після виконання першого пункту показано на табл. 12:

	1	2	3	4	5	6	7	8
a	0	0	1	0	0	0	0	0
b	12	25	0	18	∞	∞	∞	∞
c	3	3	0	3	3	3	3	3
табл. 13

Очевидно, вміст таблиці змінюється по мірі виконання загального кроку. Це видно з наступної таблиці:

		1	2	3	4	5	6	7	8
min bk=12	a	1	0	1	0	0	0	0	0
	b	12	25	0	18	∞	∞	∞	∞
	c	3	3	0	3	3	3	3	3
min bk=18	a	1	0	1	1	0	0	0	0
	b	12	25	0	18	∞	38	∞	∞
	c	3	3	0	3	3	4	3	3
min bk=25	a	1	1	1	1	0	0	0	0
	b	12	25	0	18	47	38	∞	60
	c	3	3	0	3	2	4	3	2
min bk=38	a	1	1	1	1	0	1	0	0
	b	12	25	0	18	47	38	62	60
	c	3	3	0	3	2	4	6	2
min bk=47	a	1	1	1	1	1	1	0	0
	b	12	25	0	18	47	38	61	60
	c	3	3	0	3	2	4	5	2
min bk=60	a	1	1	1	1	1	1	0	1
	b	12	25	0	18	47	38	61	60
	c	3	3	0	3	2	4	5	2

Таким чином, для вирішення ЗК потрібно n раз застосувати алгоритм Дейкстри наступним чином.

Візьмемо довільну пару вершин

j, k. Виключимо безпосереднє ребро C [j, k]. За допомогою алгоритму Дейкстри знайдемо найкоротша відстань між містами j..k. Нехай це відстань включає деякий місто m. Маємо частина туру j, m, k. Тепер для кожної пари сусідніх міст (в даному прикладі - для j, m і m, k) видалимо відповідне ребро і знайдемо найкоротша відстань. При цьому в найкоротша відстань не повинен входити вже використаний місто.

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