Материал: 62_201

На малюнку 59, а відображено перший крок виконання алго­ ритму: з вершини 1 видно вершини 2 і 7 на відстані відповідно 5 і 15. Решта вершин у поле зору ще не потрапили. На другому кроці визначаємо наступну вершину, до якої необхідно здійснити перехід. Претендентами є дві вершини з видимих: 2 і 7. Але до вершини 2 з вершини 1 ближче, тому перейдемо в неї (мал. 59, б). Тепер спробуємо подивитися на вершину 7 з вершини 2. Для цьо­ го додамо до відстані, яку ми пройшли до вершини 2 (це є число 5), пряму відстань від вершини 2 до вершини 7, тобто 7. У ре­ зультаті отримаємо 12, що є ближче, ніж безпосередня відстань між вершинами 1 і 7 - 15, яка поки що нами зафіксована. Саме тому зробимо заміну числа 15 на число 12 і зазначимо у третьо­ му рядку, що ця заміна зроблена через вершину 2.

Відмітимо вершини 1 і 2 як «відвідані» і визначимо серед видимих (мал. 59, б) найближчу. Такою є лише одна вершина з номером 7. Перейдемо в неї (мал. 60, а). Тепер нам відкрива­ ється решта вершин графа, що ми і зафіксуємо у вигляді відста­ ней до них з вершини 7. Цю відстань ми отримаємо як суму відстані до вершини 7 - 12 і відстані до кожної з видимих з неї вершин. Останню інформацію ми візьмемо із 7-го рядка таблиці суміжності. Оскільки до цього вершин 3, 4, 5, 6 не було видно, то отриманий результат запишеться у відповідні комірки.

Тепер маємо вже три відвіданих вершини і будемо визнача­ ти наступну, в яку можна перейти. Шукаємо її серед видимих з найменшою відстанню (мал. 60, а). Таких є три: 3, 4, 5. Можна вибирати будь-яку, але логічніше вибрати з меншим номером, тобто 3. З неї видно лише дві вершини: 4 і 5 (3-й рядок таблиці суміжності). Як видно з малюнка 60, б, відстань до них через

107

1

12+5=17<oo Й12+25=37<oo 17+5=22>17P -17+15=32>17

a)12+5=17<oo L 12+5=17<oo 6)

Мал. 60

вершину 3 буде більшою за вже визначену через вершину 7. То­ му на цьому кроці в значеннях поточних відстаней до вершин ніяких змін немає, лише веріпина 7 переходить до множини відвіданих (мал. 60, а).

Ч -\.

Мал. 61

Серед невідвіданих вершин 4, 5,6 претендентом на відвідуван­ ня тепер буде вершина 4. Відстань до неї вже становить 17.3 таб-

108

лиці суміжності видно невідвідані вершини 5 і 6. Відстань від вер­ шини 4 до них відповідно дорівнює 5 і 1. Враховуючи це, ми мо­ жемо виправити лише відстань до вершини 6, яка тепер стано­ витиме 18, позначивши це в третьому рядку на малюнку 61, б.

Мал. 62

На малюнку 62 вже фактично присутній результат вико­ нання алгоритму Дейкстри для пошуку найкоротшого шляху від вершини 1 до вершини 6. Тому останній крок алгоритму є дещо фіктивним: серед невідвіданих вершин лишається тіль­ ки вершина 6, в яку переходимо, і покращити результат для неї вже не можна, оскільки можемо побачити її з неї самої на відстані 0.

Результатом виконання алгоритму є відстань 18 між верши­ нами 1 і 6. А шлях можна визначити так: у вершину 6 на остан­ ньому кроці ми потрапили з вершини 4, у вершину 4 ми потрапили з вершини 7, у вершину 7 - з вершини 2, а у верши­ ну 2 - з вершини 1. Тому шлях буде таким: 6=>4=>7=>2=>1.

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

Перейдемо до питання реалізації алгоритму у вигляді про­ грами. Визначимо спочатку масиви, необхідні для коректної роботи алгоритму. їх є три: d - таблиця суміжності заданого гра­ фа, dist - значення найкоротших поточних відстаней від старто­ вої вершини st до і-ї вершини, from - номер останньої вершини

109

у наикоротшому поточному шляху до і-ї вершини. Окрім цього, необхідна буде множина s, де зберігатимуться номери невід віда­ них вершин. Опис цих змінних може бути таким:

d: аггау[1.. 100,1.. 100] of word; dist.from: аггау[1..100] of word; s: set of byte;

Тепер можемо запропонувати реалізацію алгоритму Дейкстри для визначення найкоротшого шляху між двома задани­ ми вершинами в навантаженому графі мовою Pascal:

while S <> [] do {Виконання алгоритму, поки не будуть переглянуті всі вершини графа.}

for і := 1 to n do {Перегляд усіх поточних відстаней між розглянутими вершинами.} if (і in s) and (dist[i] < min) and (dist[i] > 0) then {Визначення вершини /сз} begin min := dist[i]; k := і end; {мінімальним поточним значенням відстані.}

Перед початком безпосереднього виконання алгоритму не­ обхідно виконати деякі початкові дії. Назвемо цей блок алго­ ритму «ініціалізацією»:

S := [1 ..n]; s := S - [st]; {Підготовка множини невідвіданих вершин.} for І := 1 to П do {Перенесення у масив dist інформації про відстань до вершин,}

Для виведення найкоротшого шляху від стартової вершини до фінішної необхідно організувати такий цикл:

end;

110

За потреби можна ще вивести значення найкоротшого шля­ ху, яке знаходиться в масиві dist в елементі з порядковим номе­ ром fin:

writeln(i_out,dist[iin]);

Ми навели і покроково опрацювали алгоритм Дейкстри для зваженого неорієнтованого графа. А чи можна скористатися ним для інших графів? Наприклад, для зваженого орієнтова­ ного. Так, можна, і при цьому немає необхідності вводити до алгоритму якісь корективи. Наведений алгоритм працює і для таких графів. А якщо розглянути незважений граф, то поняття найкоротшого шляху можна тлумачити як мінімальну кіль­ кість ребер, що утворюють цей шлях. У такому разі вмістом масиву dist[i] буде саме кількість ребер, якими необхідно про­ йти із заданої вершини до вершини з номером і.

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

Тестування алгоритму Дейкстри повинно базуватися на підтвердженні ефективності його роботи, що залежить тільки від кількості вершин заданого графа. Тому необхідно підібрати різноманітні за структурою графи, які можна розбити на три групи: з кількістю вершин до 10, з кількістю вершин близько 50 і з кількістю вершин, що сягає 100. Для великих тестів бажано розробити програми, Що їх генерують.

Алгоритм Флойда-Уоршелла

З алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вер­ шин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. І це вірно. Питання лише в часі виконання такого алгоритму, оскіль­ ки його оцінка буде 0(п3). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.

Уявімо собі, що до вершин заданого графа прив'язано гумову мотузку. Спочатку будемо вважати, що відстанню між вершина­ ми і та. J є довжина цієї мотузки. Але якщо ми її розтягнемо і за­ чепимо за вершину k, то тепер відстань між вершинами і та j можна вирахувати як суму довжин між вершинами і, k та k, у.

111