б) Для пошуку шляхів від a до всіх вершин: якщо всі вершини отримали постійні мітки (включені в множину M), то ці мітки дорівнюють довжинам найкоротших шляхів, зупинитись; якщо деякі вершини мають тимчасові мітки, то перейти до кроку 2.

Обґрунтування алгоритму Дейкстри. Для доведення коректності алгоритму Дейкстри достатньо відмітити, що при кожному застосуванні кроку 3, вершина v* вибирається як мінімальна серед вершин з тимчасовими мітками. Для визначення значень цих міток (крок 2) використовувались вершини з постійними мітками, тобто вершини, для яких вже відомий найкоротший маршрут.

Проведемо доведення по індукції за кількістю застосувань кроку 3. В перший раз на кроці 3 обираються такі вершини vГ(a), тобто вершини суміжні з початковою вершиною a, для якої найкоротший шлях порожній і дорівнює 0. Нехай це справджується для кроків 2, 3, …, k – 1. На k-й ітерації кроку 3 обирається така вершина v*, для якої l(v*) = min{l(v)}, vT. Відмітимо, що якщо відомий шлях, який проходить через вершину з постійною міткою, то тим самим відомий найкоротший шлях.

Припустимо, що l(v*) більше за довжину найкоротшого шляху від a до v* (позначимо цей шлях P*, а його довжину – w(P*)), тобто l(v*) > w(P*). Тоді на цьому шляху мають бути вершини з тимчасовими мітками. Розглянемо найпершу серед них на цьому шляху – вершину v′T. Частину шляху P* від a до v′ позначимо P′, довжину P′ позначимо відповідно w(P′). Маємо: l(v′) = w(P′)  w(P*) < l(v*), тобто l(v′) < l(v*). Але це суперечить способу обрання нової вершини з постійною міткою на кроці 3.

Доведення випадку б), тобто задачі пошуку найкоротших шляхів від вершини a до всіх інших вершин графа, є аналогічним. ►

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

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

Знайдемо довжину найкоротшого шляху від початкової вершини a до вершини z у графі на рис. 30.6, а. Послідовність дій зображено на рис. 30.6, б – е, мітки записано в дужках біля кожної вершини. Вершини, які включені в множину M, обведено колами; мітки таких вершин оголошують постійними. У процесі роботи алгоритму будують два вектори: вектор l постійних міток (довжини найкоротших шляхів від вершини a до даної вершини) і вектор  вершин, з яких у дану вершину безпосередньо потрапляє найкоротший шлях. У табл. 30.1 у першому рядку містяться довільно впорядковані вершини графу, у другому – відповідні постійні мітки (компоненти вектору l), а в третьому – компоненти вектору .

---

а)	б)
в)	г)
д)	е)

Рис. 30.6. Приклад роботи алгоритму Дейкстри.

Вершини графа (елементи множини V)	a	b	c	d	e	z
Вектор l (постійні мітки вершин)	0	3	2	8	10	13
Вектор  (вершини, з яких у дану вершину заходить найкоротший шлях)	-	c	a	b	d	e

Табл. 30.1.

Постійна мітка вершини z дорівнює 13. Отже, довжина найкоротшого шляху від a до z дорівнює 13. Сам шлях знаходять за допомогою першого й третього рядків таблиці та будують у зворотному порядку. Кінцева вершин – z; у неї потрапляємо з вершини e (див. вектор ). У вершину e потрапляємо з вершини d, у d – з b та продовжуємо цей процес до вершини a: z  e  d  b  c  a. Отже, найкоротший шлях такий: a, c, b, d, e, z.

30.5. Алгоритм Белмана-Форда

Як зазначалось вище, алгоритм Дейкстри не знаходить коректно найкоротший шлях у випадку, коли граф містить ребра з негативними вагами. Пропонуємо самостійно в цьому переконатись шляхом побудови прикладу графу з негативними ребрами так, щоб алгоритм Дейкстри давав збій.

Для розв’язку задачі знаходження найкоротших шляхів у графах з негативними вагами ребер може використовуватись алгоритм Белмана-Форда. Цей алгоритм був запропонований незалежно Річардом Белманом та Лестером Фордом у 1958 та 1956 роках. Він дозволяє знаходити найкоротший шлях від заданої вершини до всіх інших вершин графу у випадку існування в графі ребер з негативними вагами. Єдиним обмеженням застосування цього алгоритму є відсутність негативних циклів у графі. Дійсно, якщо в графі є хоча б один цикл, сумарна вага ребер якого є від’ємною, то це дозволить нам знайти маршрут з якою завгодно малою довжиною між двома вершинами в графі. Алгоритм Белмана-Форда у випадку існування негативних циклів в графі дозволяє визначити цей факт та коректно завершити свою роботу.

Алгоритм Белмана-Форда заснований на ідеях динамічного програмування. В двох словах ідею динамічного програмування можна описати наступним чином. Початкова задача розбивається на менші підзадачі, які розв’язуються рекурсивно. Пізніше розв’язок початкової задачі отримується із розв’язку підзадач. Причому кожна з окремих підзадач може розв’язуватись більше ніж один раз. Для того щоб уникнути зайвою роботи в алгоритмах динамічного програмування вводяться спеціальні таблиці (матриці), які зберігають значення розв’язків вже обрахованих задач. Через це часто такі алгоритми вимагають значних ресурсів пам’яті для збереження відповідних значень.

Наразі припустимо, що у вхідному графі G немає негативних циклів. При цьому потрібно знайти відстані найкоротших маршрутів від заданої вершини a до всіх інших вершин графу. Позначимо через довжину мінімального маршруту від a до v, який містить не більше i ребер. Будемо вважати, що якщо такого маршруту не існує, то значення дорівнюватиме +.

---

Тепер розглянемо як може бути отримане значення з величин , тобто з довжин мінімальних маршрутів між a та деякими вершинами u, в яких використовується не більше (i – 1) ребер. Перший варіант – коли просто v = u, тобто . Другий варіант – коли ми розглядаємо маршрут від a до u, який містить не більше (i – 1) ребер, а також ребро (u, v). Ми шукаємо найкоротший маршрут, а тому нас цікавить мінімальне з усіх можливих значень, які отримуються у другому варіант, а також значення з першого варіанту. Таким чином

.

(30.1)

З припущення, що у графі немає негативних циклів, випливає, що найкоротші маршрути не повинні містити жодного циклу. А відтак найбільша кількість ребер, яка може бути присутня у маршрутах дорівнює n – 1, де n – кількість вершин графу. З цього факту та наведеної вище рекурентної формули слідує, що довжина найкоротшого маршруту від початкової вершини a до деякої вершини v у графі буде визначитись величиною . Щоб її обрахувати потрібно вирахувати усі значення для всіх i = 1, 2, …, n – 1 та всіх вершин vV. Саме це і відповідає ідеї динамічного програмування.

Для запису псевдокоду алгоритму Белмана-Форда використаємо двовимірний масив (матрицю) A розмірності nn, значення A[i, v] якого будуть відповідати величинам розглянутим раніше. Для базового випадку i = 0 значення масиву A ініціалізуються наступним чином: A[0, a] = 0 та A[i, v] = + для всіх vV відмінних від a. Нижче наведений псевдокод алгоритму Белмана-Форда.

for v = 1 to n A[0, v]  + A[0, a]  0 for i = 1 to n-1 for v = 1 to n A[i, v] = A[i-1, v] for всіх ребер (u, v) if A[i, v] > A[i-1, u] + w(u, v) then A[i, v]  A[i-1, u] + w(u, v)

Як видно з наведеного лістингу, формула (30.1) замінена одним внутрішнім циклом for у рядку 7. Дійсно, під час обрахунку формули (30.1) для всіх vV будуть переглянуті всі ребра графу (u, v). Відтак це можна зробити явно за допомогою одного окремого циклу.

Час роботи алгоритму Белмана-Форда становить O(mn), де n – кількість вершин та m – кількість ребер графу G. Це більше, ніж для алгоритму Дейкстри, для якого час роботи визначається як O(m lgn).

Якщо необхідно визначити не тільки відстані найкоротших маршрутів від заданої вершини до всіх інших вершин графу, а й, власне, самі маршрути, то для цього потрібно зберігати вершини-попередники для кожної вершини. Позначимо такі вершини через P[v] – вершина, яка передує вершині v у найкоротшому маршруті (аналогічно до вектору  в алгоритмі Дейкстри). Масив P ініціалізується нульовими значеннями. Тепер, коли ми оновлюємо значення A[i, v] у рядку 9, необхідно також оновлювати значення P[v], яке буде дорівнювати вершині u. По закінченню роботи алгоритму маршрут від початкової вершини a до довільної вершини v відновлюється ззаду наперед за допомогою відповідних значень масиву P.

Розглянемо приклад на рис. 30.7. Початковий граф із ініціалізованими значеннями A[0, v] наведений у частині а цього рисунку разом із початковими значеннями масиву P. На першій ітерації (i = 1) розглядаються маршрути від вершини a довжиною 1 (рис. 30.7, б): до вершини b (довжина 6) та вершини c (довжина 7). При цьому для вершин b та c значення масиву P стає рівним вершині a. На другій ітерації (i = 2; рис. 30.7, в) розглядаються маршрути довжиною 2. Тепер ми вже можемо потрапити у вершину d, причому двома шляхами: через вершину b (довжина 11 = 6 + 5) та через вершину c (довжина 4 = 7 – 3); з них обирається мінімальний і P[d] = с. Так само до вершини e можна дійти двома шляхами: через b (довжина 2 = 6 – 4) та через c (довжина 16 = 7 + 9); обирається мінімальний і P[e] = b. На третій ітерації (i = 3; рис. 30.7, г) покращується значення для вершини b, адже тепер ми можемо розглянути маршрут довжиною 3: a – c – d – b, довжина якого 2 (P[b] стає рівним d). На останній ітерації оновлюється значення для вершини e: завдяки ребру (b, e) воно стає рівним –2, а P[e] лишається рівним b.

---

Можна модифікувати алгоритм Белмана-Форда, щоб він закінчував свою роботу раніше. Дійсно, якщо на деякі ітерації i виконується умова A[i, v] = A[i – 1, v] для всіх vV, то це означає, що всі подальші ітерації ніяким чином не зможуть змінити значення A[i, v]. А отже, в цьому випадку роботу алгоритму можна закінчити раніше.

Для того, щоб алгоритм Белмана-Форда міг визначати негативні цикли в графі потрібно його трохи модифікувати. Припустимо замість того, щоб спинитись на ітерації i = n – 1, ми виконаємо ще одну додаткову ітерацію i = n. Інтуїтивно зрозуміло (і це також легко довести формально), що якщо граф G містить хоча б один негативний цикл, то значення A[n, v] повинні стати меншими за значення A[n – 1, v] для деяких vV. Отже, в кінець вище наведеного псевдокоду алгоритму Белмана-Форда потрібно додати такі рядки:

for всіх ребер (u, v) if A[n-1, v] > A[n-1, u] + w(u, v) then error “Граф містить негативні цикли”

Час роботи при цьому лишається незмінним: O(mn).

	v P(v) a – b – c – d – e –		v P(v) a – b a c a d – e –
а) i = 0		б) i = 1
	v P(v) a – b a c a d c e b		v P(v) a – b d c a d c e b
в) i = 2		г) i = 3
		v P(v) a – b d c a d c e b
д) i = 4

Рис. 30.7. Приклад роботи алгоритму Белмана-Форда.

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

Розглянемо задачу пошуку в графі найкоротшого шляху між кожною парою вершин. Звичайно, цю загальнішу задачу можна розв’язати багатократним застосуванням алгоритмів Дейкстри або Белмана-Форда з послідовним вибором кожної вершини графу як початкової. Проте є прямий спосіб розв’язання цієї задачі за допомогою алгоритму Флойда-Уоршола. У ньому довжини дуг можуть бути від’ємними, проте не може бути циклів із від’ємною довжиною.

Нехай G = (V, E) – орієнтований граф. Внутрішніми вершинами шляху a, x₁, x₂, …, x_m–1, b в графі G є вершини x₁, x₂,…, x_m–1. Пронумеруємо вершини графу цілими числами від 1 до n. Позначимо як довжину найкоротшого шляху з вершини і у вершину j, у якому як внутрішні можуть бути лише перші k вершин графу G. Якщо між вершинами і та j не існує жодного шляху, то вважатимемо, що  = . Зі сказаного випливає, що – це вага дуги (i, j), а якщо такої дуги немає, то  = . Для довільної вершини і вважатимемо  = 0. Отже, дорівнює довжині найкоротшого шляху з вершини і у вершину j. Позначимо як матрицю розмірності n  n, (і, j)-й елемент якої дорівнює . Якщо в заданому орієнтованому графі G відома вага кожної дуги, то, виходячи з попередніх міркувань, можна сформувати матрицю , елементи якої дорівнюють довжинам найкоротших шляхів між усіма парами вершин графу G.

---

В алгоритмі Флойда-Уоршола як початкову беруть матрицю . Спочатку за нею обчислюють матрицю , потім – і процес повторюють доти, доки за матрицею не буде обчислено матрицю . Розглянемо ідею, на якій ґрунтується алгоритм Флойда-Уоршола. Припустимо, що відомі:

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

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

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

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

30.2

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

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

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

2. Цикл по всіх k, що послідовно набуває значення 1, 2, …, n, визначити за елементами матриці елементи матриці , використовуючи рекурентне співвідношення (30.1).

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

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

Якщо заздалегідь відомо, що в графі G немає циклів із від’ємною довжиною, то обсяг обчислень можна дещо зменшити. У цьому разі для всіх і та всіх k має бути  = 0. Тому не потрібно обчислювати діагональні елементи матриць ,  , …,  . Окрім того, для всіх і = 1, 2, …, n справджуються співвідношення , , які випливають з того, що коли немає циклів із від’ємною довжиною, вершина k не може бути внутрішньою в будь-яких найкоротших шляхах, котрі починаються чи закінчуються в самій вершині k. Отже обчислюючи матрицю , немає потреби переобчислювати елементи k–го рядка й k–го стовпця матриці . Отже, у матриці за формулою (30.2) потрібно обчислювати лише n² – 3n + 2 елементів. Очевидно, що складність алгоритму Флойда-Уоршола становить O(n³).

Щоб після закінчення його роботи можна було швидко знайти найкоротший шлях між будь-якою парою вершин, на k-й ітерації разом із матрицею побудуємо матрицю . Спочатку беремо  = i для всіх і, j = 1, …, n, ij;  = 0. Далі, на k-й ітерації візьмемо , якщо , і , якщо . Отже, – номер вершини, яка є перед вершиною j у поточному [i, j]–шляху, тобто найкоротшому [i, j]–шляху, усі вершини якого містяться в множині {1, 2, …, k}. Матриця відіграє ту саму роль, що й вектор  в алгоритмі Дейкстри. За допомогою матриці вершини, через які проходить найкоротший [i, j] – шлях, визначають так: i, .., j₃, j₂, j₁, j, де , , …

---

Смотрите также файлы

• 35_Merezhi_ta_potoki.doc

• 37_Gramatiki.doc

• 38_Skinchenni_avtomati.doc

• dinamika.docx

• dinamika_1.docx