Обґрунтування алгоритму Дейкстри

Мітка вершини v (l(v)!= ) дорівнює довжині <a,v> - шляху, побудованого за алгоритмом до певного моменту. Тому достатньо довести, що постійна мітка l(v) кожної вершини v дорівнює довжині найкоротшого <a,v> - шляху. Отже, доведемо що значення l(v) – постійної мітки вершини v- дорівнює довжині найкоротшого шляху від початкової вершини a до вершини v. Для доведення цього застосуємо математичну індукцію.

Нехай вершина v одержала свою постійну мітку на k-й ітерації, тобто після k-го виконання кроку 4 алгоритму Дейкстри. У разі k = 1 твердження очевидне. Припустимо, що воно справджується для вершин, які отримали свої постійні на ітераціях із номерами 2,3,…,k-1. Позначимо як Р0 шлях від a до v, побудований з алгоритмом Дейкстри за k ітерацій, а як Р* - найкоротший шлях від a до v. Довжину шляху Р позначатимемо як w(P). За умовою w(Р0) = l(v). Нехай М і Т = V\M – множини вершин відповідно з постійними та тимчасовими мітками перед початком k-ї ітерації.

Розглянемо ситуацію перед початком k–ї ітерації. Можливі два випадки.

 

Випадок 1. Деякі вершини шляху Р* належать множині Т. Нехай - перша (починаючи від a) з тих вершин шляху Р*, які належать множині Т, а вершина v ’ безпосередньо передує на шляху Р*. За вибором маємо, що v ‘ є М. Позначимо як Р₁* частину шляху Р* від a до . За припущенням індукції l(v ‘) – довжина найкоротшого шляху від a до v ’. Тому w(P₁*) = l(v ‘, )> = l() (нерівність зумовлена кроком 2). Оскільки l() – тимчасова мітка, а постійну мітку l(v) вершини v вибрано на k-й ітерації, як найменшу з тимчасових (крок 3), то l()>=l(v). Об’єднавши дві останні нерівності, одержимо w(P*)<=w(P₁*); отже, w(P*) = w(Р0), тобто Р0 – найкоротший шлях від початкової вершини a до вершини v.

Випадок 2. Усі вершини шляху Р* містяться в множині М. Нехай v‘ та v* - вершини, які безпосередньо передують вершині v відповідно в шляхах Р* та Р₀. Позначимо як P ’ частину шляху Р* від початкової вершини a до вершини v ‘. За припущенням індукції w(P ‘) >= l(v ’), то w(P*) = w(P ’) + w(v ‘, v) >= l(v ‘) + e(v ’, v) = w(Р₀).

Припустимо тепер, що v ’!= v*. Позаяк v одержує постійну мітку l(v) з v*, а не з v ‘, то w(P*) = l(v ’) + w(v ‘, v) >= l(v*, v) = w(Р₀).

Отже, і у випадку 2 справджується нерівність w(P*) >= w(Р₀), тобто Р₀ – найкоротший шлях від a до v.

Якщо граф подано матрицею суміжності, складність алгоритму Дейкстри становить О(n²). Коли кількість дуг m значно менша ніж n², то найкраще подавати орієнтований граф списками суміжності. Тоді алгоритм можна реалізувати зі складністю О(m log n), що в цьому разі істотно менше, ніж О(n²).

Алгоритм Дейкстри дає змогу обчислити довжину найкоротшого шляху від початкової вершини a до заданої вершини z. Для знаходження самого шляху потрібно лише нагромаджувати вектор вершин, з яких найкоротший шлях безпосередньо потрапляє в дану вершину. Для цього з кожною вершиною v графа G, окрім вершини a, зв’язують іще одну мітку – О(v). Крок 2 модифікують так. Для кожної вершини v є Г(х)\М якщо l(v) >l(x) + w(x, u), то l(v):= l(x) + w(x, u) та О(v):= x, а ні, то не змінювати l(v) та О(v). Коли мітка l(v) стане постійною найкоротший <a,v> - шлях буде потрапляти у вершину v безпосередньо з вершини х. Із постійних міток l(v) та О(v) утворюють вектори l і O.

 

Приклад 3.33. Знайдемо довжину найкоротшого шляху від початкової вершини а до вершини z у графі на рис. 3.37, а. Послідовність дій зображено на рис. 3.37, б-е, мітки записано в дужках біля вершин. Вершини, які включено в множину М, обведено кружечками; мітки таких вершин оголошують постійними. У процесі роботи алгоритму будують два вектори: вектор l постійних міток (довжини найкоротших шляхів від вершини а до даної вершини) і вектор вершин, з яких у дану вершину безпосередньо потрапляє найкоротший шлях. У табл. 3.4 в першому рядку містяться довільно впорядковані вершини графа, у другому — відповідні постійні мітки (компоненти вектора l), а в третьому — компоненти вектора . Постійна мітка вершини z дорівнює 13. Отже, довжина найкоротшого шляху від а до z дорівнює 13. Сам шлях знаходять за допомогою першого й третього рядків таблиці та будують у зворотному порядку. Кінцева вершина — z, у неї потрапляємо з вершини е (див. вектор ). У вершину е потрапляємо з вершини d, у d — з b та продовжуємо цей процес до вершини а: z←е←d←b←с←а. Отже, найкоротший шлях такий: а, с, b, d, e, z.

 

 

 

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

Таблиця 3.4

Вершини графа (елементи множини V)	а	b	с	d	е	z
Вектор l (постійні мітки вершин)
Вектор (вершини, з яких у дану вершину заходить найкоротший шлях)	-	с	а	b	d	е

 

Ми розглянули задачу відшукання в графі найкоротшого шляху від якоїсь виділеної (початкової) вершини до будь-якої іншої. Розглянемо задачу пошуку в графі найкоротшого шляху між кожною парою вершин. Звичайно, цю загальнішу задачу можна розв'язати багатократним застосуванням алгоритму Дейкстри з послідовним вибором кожної вершини графа як початкової. Проте є й прямий спосіб розв'язання цієї задачі за допомогою алгоритму Флойда. У ньому довжини дуг можуть бути від'ємними, проте не може бути циклів із від'ємною довжиною. Нехай G= (V, E) — орієнтований граф. Нагадаємо, що внутрішні вершини шляху a, x_1, x₂, x_m-u в графі G — х₁, х₂, …, х_m-1. Наприклад, внутрішні вершини шляху а, с, d, а, f, b — с, d, а, f. Пронумеруємо вершини графа цілими числами від 1 до n. Позначимо як довжину найкоротшого шляху з вершини і у вершину j, у якому як внутрішні можуть бути лише перші k вершин графа G. Якщо між вершинами і тa j не існує жодного такого шляху, то умовно вважатимемо, що = . Зі сказаного випливає, що — це вага дуги (ij), а якщо такої дуги немає, то = . Для довільної вершини i вважатимемо = 0. Отже дорівнює довжині найкоротшого шляху з вершини і у вершину j. Позначимо як W nxn матрицю, (і, j)-й елемент якої дорівнює . Якщо в заданому орієнтованому графі G відома вага кожної дуги, то, виходячи з попередніх міркувань, можна сформувати матрицю W⁽⁰⁾. Тепер потрібно визначити матрицю W⁽ⁿ⁾, елементи якої дорівнюють довжинам найкоротших шляхів між усіма парами вершин графа G.

В алгоритмі Флойда як початкову беруть матрицю W⁽⁰⁾. Спочатку за нею обчислюють матрицю W⁽¹⁾ потім — W⁽²⁾, і процес повторюють доти, доки за матрицею W^(n-1) не буде обчислено матрицю W⁽ⁿ⁾ Розглянемо ідею, на якій ґрунтується алгоритмі Флойда. Припустимо, що відомі.

 

1. Найкоротший шлях із вершини і у вершину k, у якому як внутрішні використано лише перші (k-1) вершин.

2. Найкоротший шлях із вершини k у вершину j, у якому як внутрішні використано лише перші (k - 1) вершин.

3. Найкоротший шлях із вершини і у вершину j, у якому як внутрішні використано лише перші (k - 1) вершин.

Оскільки за припущенням граф G не містить циклів із від'ємною довжиною, то один із двох шляхів — шлях із п. 3 чи об'єднання шляхів із пп. 1 і 2 — найкоротший шлях із вершини і у вершину j, у якому як внутрішні використано лише перші (k - 1) вершин. Отже,

 

(3.1)

 

Зі співвідношення (3.1) видно, що для обчислення елементів матриці w потрібні тільки елементи матриці W . Тепер ми можемо формально описати алгоритм Флойда для знаходження в графі найкоротших шляхів між усіма парами вершин.

 

Алгоритм Флойда

Наведемо кроки алгоритму.

Крок 1. Присвоювання початкових значень. Пронумерувати вершини графа Gцілими числами від 1 до n. Побудувати матрицю W⁽⁰⁾= W, задавши кожний її (i,j)-елемент такий, що дорівнює вазі дуги, котра з'єднує вершину і з вершиною j. Якщо в графі G ці вершини не з'єднано дугою, то виконати := . Крім того, для всіх і виконати := 0.

Крок 2. Цикл. Для k, що послідовно набуває значення 1, 2, …, п, визначити за елементами матриці W^(k-1) елементи матриці W^(k) використовуючи рекурентне співвідношення (3.1).

Після закінчення цієї процедури (і,j) - елемент матриці W⁽ⁿ⁾ дорівнює довжині найкоротшого шляху з вершини і у вершину j.

Якщо під час роботи алгоритму для якихось k й і виявиться, що < 0, то в графі G існує цикл із від'ємною довжиною, який містить вершину і. Тоді роботу алгоритму потрібно припинити.

Якщо заздалегідь відомо, що в графі Є немає циклів із від'ємною довжиною, то обсяг обчислень можна дещо зменшити. У цьому разі для всіх і та всіх k має бути =0. Тому не потрібно обчислювати діагональні елементи матриць W⁽¹⁾,W⁽²⁾, …, W⁽ⁿ⁾. Окрім того, для всіх і = 1, 2, …, п справджуються співвідношення = , = які випливають із того, що коли немає циклів із від'ємною довжиною, вершина k не може бути внутрішньою в будь-яких найкоротших шляхах, котpі починаються чи закінчуються в самій вершині k. Отже, обчислюючи матрицю немає потреби переобчислювати елементи k-го рядка й k-го стовпця матриці W^(k-1). Отже, у матриці W^(k) за формулою (3.1) потрібно обчислювати лише k² – З × п + 2 елементи. Очевидно, що складність алгоритму Флойда становить 0(п³). Щоб після закінчення його роботи можна було швидко знайти найкоротший шлях між будь-якою парою вершин, на k-й ітерації разом із матрицею W^(k) побудуємо матрицю ^(k) =[ ]. Спочатку беремо :=і для всіх і,j= 1, …, п, ; := 0. Далі, на к-й ітерації візьмемо = , якщо = і = , якщо = + . Отже, — номер вершини, яка є перед вершиною j у поточному (i, j) - шляху, тобто найкоротшому (i, j) - шляху, усі внутрішні вершини якого містяться в множині (1, 2, …, k). Матриця ⁽ⁿ⁾ =[ ] відіграє ту саму роль, що й вектор в алгоритмі Дейкстри. За допомогою матриці ^(k) вершини, через які проходить найкоротший (i, j) - шлях, визначають так: i, …, j₃, j₂, j₁, j, де j₁= , j₂= , j₃₌ , ….

Приклад 3.34. Знайти найкоротші шляхи між усіма парами вершин орієнтованого графа на рис. 3.38.

Рис. 3.38 Граф до прикладу 3.34

 

Нижче наведено результати виконання кожної з чотирьох

 

 

W⁽⁰⁾= W= ⁽⁰⁾=

 

 

 

W⁽¹⁾= ⁽¹⁾=

 

 

 

W⁽²⁾= ⁽²⁾=

 

 

 

W⁽³⁾= ⁽³⁾=

 

 

 

W⁽⁴⁾= ⁽⁴⁾=

 

Матриця W⁽⁴⁾ дає довжини найкоротших шляхів між усіма парами вершин графа на рис. 3.38. Зокрема, , тобто довжина найкоротшого шляху від вершини 2 до вершини 1 дорівнює 3. Для знаходження самого шляху скористаємося матрицею ⁽⁴⁾ та запишемо у зворотному порядку вершини, через які він проходить: = 4, = 3, = 2. Отже, найкоротший шлях із вершини 2 у вершину 1 проходить через вершини 2, 3, 4, 1.

Очевидно, що як алгоритм Дейкстри, так і алгоритм Флойда можна застосовувати без жодних змін і до неорієнтованих графів. Для цього достатньо кожне ребро {и, V}, що має вагу (и, V), розглядати як пару дуг (и, V) та (V, и) з тією самою вагою. Слід ураховувати, що неорієнтоване ребро із від'ємною вагою одразу приводить до циклу із від'ємною довжиною, що робить алгоритм Флойда незастосовним.

 

Обхід графів

Існує багато алгоритмів на графах, які ґрунтуються на систематичному переборі їх вершин або обході вершин, під час якого кожна вершина одержує унікальний порядковий номер. Алгоритми обходу вершин графа називають методами пошуку [23].

3.9.1. Пошук углиб у простому зв'язному графі

Опишемо метод пошуку в простому зв'язному графі, який являє собою одну з основних методик проектування алгоритмів, пов'язаних із графами. Цей метод називають пошуком углиб, або DFS - методом (від англ. depth first search).

 

Нехай G = (V, Е) — простий зв'язний граф, усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинам графа G надають номери (DFS - номери) та певним способом позначають ребра. У ході роботи алгоритму використовують структуру даних для збереження множин, яку називають стеком (англ. stack — стіг). Зі стеку можна вилучити тільки той елемент, котрий було додано до нього останнім: стек працює за принципом «останнім прийшов — першим вийшов» (last in, first out — скорочено LIFO). Інакше кажучи, додавання й вилучення елементів у стеку відбувається з одного кінця, який називають верхівкою стеку. DFS - номер вершини х позначають DFS(x).

 

 

Таблиця 3.5

Вершина	DFS - номер	Вміст стеку
Ь		Ь
С		be
D		bed
А		beda
-	-	bed
-	-	be
F		bef
Е		befe
G		befeg
-	-	befe
-	-	bef
-	-	be
H		bch
-	-	be
-	-	b
-	-