Між двома заданими вершинами

Нехай є орієнтований граф G = (V, Е), у якого всі дуги мають позитивні мітки (вартості дуг), а одна вершина визначена як джерело. Завдання полягає в пошуку вартості найкоротших шляхів від джерела до всіх інших вершин графа G. Ця задача часто називається задачею пошуку найкоротшого шляху з одним джерелом іможе показатися, що більш природною задачею буде пошук найкоротшого шляху від джерела до визначеної вершини призначення. Але ця задача в загальному випадку має такий же рівень складності, що і задача пошуку найкоротшого шляху для усіх вершин графа (за винятком того "щасливого" випадку, коли шлях до вершини призначення буде знайдений раніше, чим переглянуті шляхи до усіх вершин графа).

Представимо граф G у виді карти маршрутів рейсових польотів з одного міста в іншій, де кожна вершина відповідає місту, а дуга v —> w - рейсовому маршруту з міста v у місто w. Мітка дуги v —> w - це час польоту з міста v у місто w. При цьому може виникнути припущення, що в даному випадку як модель більше підходить неорієнтований граф, оскільки мітки дуг v —> w і w —> v можуть збігатися. Але фактично в більшості випадків час польоту в протилежних напрямках між двома містами різний. Крім того, допущення про збіг міток дуг v —> w і w —> v принципово не впливає на рішення поставленої задачі.

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

Алгоритм будує множину S вершин, для яких найкоротші шляхи від джерела уже відомі. На кожному кроці до множини S додається та з вільних вершин, відстань до який від джерела менше, ніж для інших вершин, що залишились. Якщо вартості всіх дуг позитивні, то можна бути упевненим, що найкоротший шлях від джерела до конкретної вершини проходить тільки через вершини множини S. Назвемо такий шлях особливим. На кожному кроці алгоритму використовується також масив D, у який записуються довжини найкоротших особливих шляхів для кожної вершини. Коли множина S буде містити усі вершини орграфа G, тобто для усіх вершин будуть знайдені "особливі" шляхи, тоді масив D буде містити довжини найкоротших шляхів від джерела до кожної вершини.

Алгоритм Дейкстри представлений у лістингу 1. Тут передбачається, що в орграфе G вершини пронумеровані цілими числами, тобто ми маємо множину вершин V= {1, 2, ..., п), причому вершина 1 є джерелом. Масив C— це двовимірний масив вартостей, де елемент C[i, j] дорівнює вартості дуги i —> j. Якщо дуги i —> j не існує, то C[i, j] полягає рівним (нескінченності), тобто більшим будь-якої фактичної вартості дуг. На кожному кроці D[i] містить довжину поточного найкоротшого особливого шляху до вершини i.

Лістинг 1. Алгоритм Дейкстри

procedure Dijkstra;

Begin

(1) S:= {1};

(2) for i:= 2 to n do

(3) D[i]:=C[l, i]; { ініціалізація D }

(4) for i:= 1 ton -1 do

Begin

(5) вибір з множини V\S такої вершини w,що значення D[w]

мінімально;

(6) додати w до множини S;

(7) for кожна вершина v з множини V\S do

(8) D[v]:= min(D[v], D([w] + C[w, v] )

End

end; { Dijkstra }

Застосуємо алгоритм Дейкстри для орграфа, показаного на рис. 2.

							Рис. 2. Орграф з позначеними дугами

На початку S = {1}, D[2] = 10, D[3] = , D[4] = 30 і D[5]= 100. На першому кроці циклу (рядки (4) - (8) лістінге 1) w = 2, тобто вершина 2 має мінімальне значення в масиві D. Потім обчислюємо D[3] = min( , 10 + 50) = 60; D[4] = min(30, 10 + ) = 30 і D[5] = min(100, 10 + ) = 100. Послідовність значень елементів масиву D після кожної ітерації циклу показані нижче:

Ітерація S wD[2] D[3] D[4] D[5]

Початок	{1}	-
	{1,2}
	{1, 2, 4}
	{1, 2, 4, 3}
	{1, 2, 4, 3, 5}

Примітка: затемненими показані найкоротші відстані від 1-ої вершини до кожної з вершин, котрі вже знаходяться у множині S

Нескладно внести зміни в алгоритм так, щоб можна було визначити сам найкоротший шлях (тобто послідовність вершин) для будь-якої вершини. Для цього треба ввести ще один масив Р вершин, де P[v] містить вершину, що безпосередньо передує вершині v унайкоротшому шляху. Спочатку покладемо Р[v] = 1 для всіх v 1. У лістингу 1 після рядка (7) треба записати умовний оператор з умовою D[w] + C[w, v] < D[v], при виконанні якого елементу P[v] привласнюється значення w. Після виконання алгоритму найкоротший шлях до кожної вершини можна знайти за допомогою зворотного проходження по попереднім вершинах масиву Р.

Наприклад, для орграфа з рис. 2 масив Р має наступні значення: Р[2] = 1, Р[3] = 4, Р[4] = 1 і Р[5] = 3 . Для визначення найкоротшого шляху, наприклад від вершини 1 до вершини 5, треба відстежити в зворотному порядку попередні вершини, починаючи з вершини 5. На підставі значень масиву Р визначаємо, що вершині 5 передує вершина 3, а вершині 3 - вершина 4, а їй, у свою чергу, - вершина 1. Таким чином, найкоротший шлях з вершини 1 у вершину 5 складає наступна послідовність вершин: 1, 4, 3, 5.

6.2. Задача пошуку найкоротших шляхів