Главная

Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Алгоритми пошуку найкоротших шляхів


Розподіл каналів і потоків інформації намережі зв’язку проводиться з урахуванням характеристики шляху. Для оцінки вагової характеристики шляху використовуються критерії, наприклад, довжина шляху, число транзитних ділянок (ранг) шляху, якість тракту передачі, надійність, передачі інформації і т.д. Найпоширенішими методами розподілу є методи, що використовують «найкоротші» шляхи. Термін «найкоротший шлях» є достатньо умовним, оскільки під найкоротшим розуміють шляхи, найкоротші по довжині, з мінімальним числом транзитних ділянок, з максимальною пропускною здатністю, шляхи мінімальної вартості, максимальної надійності .

У графі, що представляє мережу, виділена деяка вершина і, звана витоком.

Рисунок 2.2 – Зображення дерева для вершини-витоку 1

 

Рисунок 2.3 – Зображення шляху від вершини i до вершини j через проміжні

вершини х1, …, хk

 

Кожному шляху (i, ..., j), що сполучає вершину-витік i з вершиною-стоком j , ставиться у відповідність величина w (i, ..., j), звана вагою шляху. Таким чином, на безлічі всіх шляхів графа G= (X, А), сполучаючих витік i із стоком j, визначена вагова функція W (i. j) вершини j приймаюча значення w (i, ..., j) на шляху µi j = (i, ..., j). Шлях, на якому W (i. j) досягає екстремального значення, називається екстремальним (найкоротшим, або оптимальним) шляхом з i в j.

Всі методи вибору найкоротших шляхів, розвинені в теорії потоків, основані на достатньо очевидному твердженні про те, що якщо найкоротший шлях µi j від довільної вершини i до вершини j проходить через проміжні вершини х1, …, хk (рис. 2.3), то найкоротші шляхи µх1 j , …, µхk, j від вершин х1, …, хk до вершини j, відповідно, є частинами найкоротшого шляху від i до j [6].

Якщо довжина шляху µх1 j рівна Lx1, j , то довжина шляху з i до j

 

Li j = li,х1 + Lх1,j.

Тут li,х1 - довжина гілки зв'язку вершин і та Оскільки шлях µi j є найкоротшим, то

де n - число вершин графа.

Легко зрозуміти, що для знаходження найкоротшого шляху від вершини х0 до вершини хm необхідно проглянути всі можливі шляхи і вибрати той, який має екстремальну вагу.

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

 

2.2.1 Матричні алгоритми пошуку найкоротших шляхів

Зведення матриці L в степінь. Матричний метод визначення довжин найкоротших шляхів, дозволяючий знайти довжини найкоротших шляхів між всіма вершинами графа одночасно, ґрунтується на застосуванні операцій над матрицями довжин L [6, 7].

Нехай задана мережа зв'язку у вигляді графа, зображеного на рис. 2.4, цифри на ребрах якого відповідають довжинам гілок. Тоді матриця довжин L матиме вид табл. 2.3.

По суті матриця L - це матриця відстаней безпосередніх зв'язків, тобто шляхів першого рангу. Позначимо матрицю L(1). Зведемо матрицю L(1) в квадрат:

 

L(2)= L(1)· L(1). i - j-й елемент матриці L(2) визначається за правилом:

 

(2.3)

 

Таблиця 2.3 – Матриця довжин L

 

12 3 4 5

 

Рисунок 2.4 – Зображення мережі зв’язку у вигляді графа

 

Рисунок 2.5 – Зображення а) двухтранзитного шляху з вершини i до вершини j через проміжну вершину k ; б) чотирьох двухтранзитних шляхів

 

 

Інтерпретуючи тепер множення як послідовне, а складання - як паралельне з'єднання гілок (по аналогії із зведенням структурної матриці В в степінь, розділ 2.1.1), легко зрозуміти, що співмножник відповідає двохтранзитному шляху (шляхи другого рангу), який проходить з вершини i у вершину j через проміжну вершину k (рис.2.5,а),а сума, наприклад, чотирьох співмножників

 

 

- чотирьом двохтранзитним шляхам (рис. 2.5,6). Відзначимо, що співмножники і фактично відповідають однотранзитним шляхам (тобто шляхам першого рангу, включаючим тільки одну гілку).

Оскільки довжина шляху, що складається з декількох гілок, визначається сумою довжин гілок, то необхідно при множенні матриці L(1) операцію множення у виразі (2.3) замінити на операцію складання, тобто замість матимемо .

За наявності декількох паралельних одно - і двох - транзитних шляхів (див. рис. 2.5,6) для визначення довжини найкоротшого шляху необхідно операцію складання у виразі (2.3) замінити на операцію вибору мінімуму з довжин всіх одно - і двохтранзитних шляхів, тобто замість (2.3) матимемо:

 

(2.4)

 


Таким чином, елемент матриці L(2) рівний довжині найкоротшого шляху з i в j серед всіх одно - і двохтранзитних шляхів.

При зведенні матриці L(1) в степінь q при використанні операції (2.4) одержимо L(q) = L(q-1)· L(1), елемент якої визначає довжину найкоротшого шляху між вершинами і та j серед всіх шляхів першого, другого, q-гo рангу.

Зведення матриці L(1) в степінь максимального рангу Rmax приводить до отримання матриці найкоротших по довжині шляхів між всіма парами вершин графа, або матриці оптимальних шляхів Lопт = L(Rmax) .

Якщо при зведенні матриці L(1) в деяку степінь q виявиться, що

 

L(q) = L(q-1) (2.5)

процес обчислень слід припинити, оскільки при рівності (2.5) завжди виконується рівність L(q) = L(q+1) .

Таким чином, Lопт = L(q) = L(q-1)

Для даного прикладу (див. табл. 2.3) обчислимо L(2).

 

 

 

 

і т.д.

Обчисливши решту елементів матриці L(2) ,одержимо

 

12 3 4 5

 

Оскільки L(2) ≠ L(1) і показник степеня «2» < Rmax = 4, процес обчислення Lопт необхідно продовжити, обчисливши L(3) = L(2)· L(1).

Елемент матриці L(3)

 

Обчисливши решту елементів матриці L(3), отримаємо:

 

12 3 4 5

 

З порівняння L(3) і L(2) витікає, що L (3) = L(2). Таким чином, Lопт = L (3) = L(2). Матрицю Lопт називають також дистанційною і позначають D = [ dij ] [6]. Процедуру (2.4) можна застосувати для отримання шляхів мінімальної вартості, часу передачі інформації і т.д. адитивних критеріїв оптимальності шляхів, додавши елементам lij матриці L відповідне значення вартості, часу передачі інформації по гілці (і,j) і інших характеристик.

Для отримання матриці шляхів мінімального рангу Rопт між всіма вершинами графа для початкового графа необхідно побудувати матрицю безпосередніх зв'язків, або матрицю шляхів першого рангу R = [rij]. Матриця R будується аналогічно матриці L, проте замість довжини гілки зв'язку у відповідній позиції записується «1»:

Для графа рис. 2.4 матриця R має вид табл. 2.4.

 

Таблиця 2.4 – Матриця R

 

12 3 4 5

 

Всі правила, розглянуті для отримання матриці Lопт справедливі і для матриці Rопт , а саме:

Rопт =R(Rmax)

і, крім того, якщо для деякої степені q справедливе R(q) = R (q-1) , то з цього виходить, що Rопт = R(q) = R (q-1).

Помітимо також, що при зведенні матриці R(1) в будь-який степінь q R(q) = R (q-1) · R(1) операцію (2.4) слід застосовувати лише до тих елементів матриці R (q-1) , які ще не визначені, тобто .Як тільки при зведенні в чергову степінь q матриці R(l) всі елементи (і, j = , граф G - зв'язний), процес обчислення Rопт слід припинити.

Одержана матриця R(q) = Rопт.

Слід зазначити, що розглянутий метод дозволяє визначити довжини (ранги, вартості і т. д.) найкоротших шляхів між всіма вершинами графа, але не указує ті гілки, які входять в найкоротші шляхи.

Алгоритм Флойда. Алгоритм Флойда [1, 6, 8] дає можливість одержати як матрицю довжин найкоротших відстаней Lопт = D, так і маршрутну матрицю, що визначає вершини (гілки) графа, утворюючі шляхи.

Алгоритм Флойда працює таким чином. Спочатку за довжину найкоротшого шляху між довільними вершинами i і j приймається довжина гілки lij , що сполучає ці вершини. Потім послідовно перевіряються всілякі проміжні вершини, розташовані між i і j. Якщо довжина шляху, що проходить через деяку проміжну вершину k, менше попереднього (поточного) значення, яке було позначене, наприклад, dij, то змінній dij привласнюється нове значення. Зазначимо, що початкове значення dij = lij . Дана процедура повторюється для всіх пар вершин, поки не будуть набуті всі значення матриці Lопт = D.

Для будь-яких трьох різних вершин i, k і j сформульовані умови можуть бути записані у вигляді нерівності

 

dik + dkj ≥ dij (i ≠ k ≠ j)(2.6)

оскільки інакше найкоротший шлях з вершини і у вершину j повинен містити вершину k і тоді величина dij не дорівнювала би довжині найкоротшого шляху. Рис. 2.6 ілюструє виконання процедури порівняння (2.6) для пари вершин i і j.

 

Рисунок 2.6 – Зображення виконання процедури порівняння (2.6) для пари

вершин i і j

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

Алгоритм Флойда дозволяє вирішувати задачу отримання найкоротших шляхів між всіма вершинами графа для графа з n вершин за n ітерацій.

Спосіб отримання на q-й ітерації величини може бути описаний за допомогою наступної тримісної операції (операції трикутника):

(2.7)

Якщо операцію (2.7) виконувати з даною парою вершин i і j івсіма вершинами k (i ≠ k ≠ j) у порядку зростання номерів k,, то значення , одержане на останній ітерації, буде рівне довжині найкоротшого шляху з вершини i у вершину j.

На кожній ітерації алгоритму будується дві матриці.

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

Потім, виконуючи тримісну операцію (2.7) зі всіма елементами матриці D0, одержуємо D1 і т. д., до тих пір, поки для кожної пари вершин не буде виконаний критерій оптимальності (2.6).

Друга матриця, звана матрицею маршрутів (позначимо її Г ), служить для знаходження проміжних вершин (якщо такі є) найкоротших шляхів. На q-й ітерації вона визначається як , де - перша проміжна вершина найкоротшого шляху з i в j, вибирана з вершин множини {1, 2, ..., k} (i ≠ k ≠ j). Алгоритм починає роботу при , де . На q-й ітерації вершина може бути одержана із співвідношення

Після побудови матриць D0 і Г° потрібно для кожного k = 1, 2, ..., n , використовуючи для обчислень елементи матриці D q-1, одержаної на (q - 1) -й ітерації, виконати наступну процедуру.

Крок 1. Викреслити елементи k -го рядка і k -го стовпця. Назвемо цю безліч елементів базовим рядком і базовим стовпцем.

Крок 2. Для кожного елементу (i ≠ k) матриці D q-1, починаючи з першого, розташованого в лівому верхньому кутку матриці, перевірити виконання нерівності

(2.8)

 

Якщо нерівність (2.8) виконується, то вибрати нові значення i і j і знову виконати крок 2.

Якщо нерівність (2.8) не виконується, то елементу матриці D q привласнити значення = ,а єлементу матриці Гq привласнити значення = k .

Після перевірки нерівності (2.8) для всіх елементів (і, j) знов перейти до виконання кроку 1 при q = q + 1 до q = n.

Рисунок 2.7 – Зображення графа для ілюстрації роботи алгоритму Флойда

Відповідно до (2.7), при отриманні D q з D q-1 тримісну операцію, що дозволяє встановити факт приналежності базового вузла k найкоротшого шляху, слід виконувати тільки з елементами матриці D q-1 тими, що не належать ні базовому рядку, ні базовому стовпцю.

Для ілюстрації роботи алгоритму Флойда визначимо найкоротші шляхи між всіма парами вершин графа, зображеного на рис. 2.7.

Початкові значення елементів матриці D0 представлені в табл. 2.5, матриці Г° - в табл. 2.6.

 

Таблиця 2.5 – Початкові значення елементів матриці D0

 

1 2 3 4 5 6 7 8

Таблиця 2.6 – Початкові значення матриці Г°

1 2 3 4 5 6 7 8

Ітерація 1. Вершина k = 1 визначається як базова, отже, в матриці D0 викреслюємо перший рядок і перший стовпець. Оскільки в базовому рядку в стовпцях 3, 5, 6, 7, 8 містяться елементи, рівні ∞, то елементи цих стовпців можна не досліджувати відповідно до виразу (2.7).

 

 
           
         
               
         
               
               
               
               

 

Базовий рядок
Базовий стовпець

Рисунок 2.8 – Зображення елементів матриці D0

У базовому першому стовпці в рядках 3, 5, 6, 7, 8 містяться елементи, рівні ∞, тому, відповідно до (2.7), елементи цих рядків можна не досліджувати. Для того, щоб визначити, чи приведе використання вершини 1 до найбільш коротших шляхів, ніж ті, які записані в D0, слід досліджувати за допомогою трьохмісної операції (2.7) лише елементи матриці D0, зображені на рис. 2.8, а саме елементи .

Але оскільки елементи головної діагоналі (i = j) можна не розглядати, застосування операції (2.7) дає наступні результати:

Оскільки

 

і

 

то вказані елементи поміщаються в матрицю D1, вся решта елементів матриці D0 переноситься в D1 без зміни. Елементи матриці Г1 при цьому: і (q = 1), решта елементів Г1 рівна відповідним елементам матриці Г°.

Матриці D1 і Г1 представлені в таблицях 2.7 і 2.8, відповідно.

 

Таблиця 2.7 – Матриця D1

1 2 3 4 5 6 7 8

 

Таблиця 2.8 – Матриця Г1

1 2 3 4 5 6 7 8

 

Ітерація 2. Визначаємо вершину 2 як базову і викреслюємо в матриці D1 другий рядок і другий стовпець. Оскільки в другому рядку в стовпцях 6, 7 і 8 містяться ∞, відповідні стовпці не розглядаються. Оскільки в другому стовпці в рядках 6, 7 і 8 містяться ∞, відповідні рядки не розглядаються. Крім того, не розглядаються елементи головної діагоналі. В результаті необхідно досліджувати елементи , , , , , , , , , , , . Нові оцінки одержують лише наступні елементи:

Отже 2

Матриці D2 і Г2 приведені в таблицях 2.9 і 2.10.

 

Таблиця 2.9 – Матриця D2

1 2 3 4 5 6 7 8

 

Таблиця 2.10 – Матриця Г2

1 2 3 4 5 6 7 8

 

Виконуючи аналогічні обчислення на ітераціях 3, 4, 5, 6, 7, 8, отримаємо результат – матриці D і Г. Розв’язок, отриманий на ітерації 5, не поліпшується на послідуючих ітераціях. Отже, оптимальним розв’язком є: D= D5 , Г = Г5 .

 

Таблиця 2.11 – Матриця D

 

1 2 3 4 5 6 7 8

 

Таблиця 2.12 – Матриця Г

1 2 3 4 5 6 7 8

Матриці D і Г приведені в таблицях 2.11 і 2.12

Нехай необхідно визначити найкоротший шлях d15. Довжина шляху .Для знаходження відповідної послідовності вершин, що становлять шлях, звернемося до матриці Г. Оскільки то вершина 4 є першою проміжною в найкоротшому шляху з вершини 1 до вершини 5. Потім знаходимо наступну вершину на шляху до вершини 5, звертаючись до елементу γ45 = 3, далі γ35=5, отже, послідовність вершин шляху µ15 визначена: µ15={1, 4. 3, 5}.

Аналогічно визначається решта найкоротших шляхів. Наприклад, довжина шляху µ82= d82=15, шлях складається з вершин: µ82 = {8, 5, 3, 2}.

Алгоритм, заснований на застосуванні операцій булевої алгебри. Алгоритм пошуку найкоротших по рангу (транзитності) шляхів заснований на застосуванні операцій булевої алгебри (логічних операцій) до матриці зв'язності графа[9] . Пошук найкоротших шляхів в алгоритмі здійснюється по матриці А'= [а ij ], одержуваної шляхом перетворення початкової матриці зв'язності А = [а ij]. У матриці А' ненульовими являються тільки елементи, відповідні ребрам графа, що входить хоча б в один найкоротший по транзитності (рангу) шлях від фіксованої вершини-витоку у всю решту вершин-стоків графа. Перетворення матриці А в матрицю А' здійснюється виконанням операцій логічного складання, логічного множення, заперечення рівнозначності, інверсії рядків матриці А.

Перетворення матриці А в матрицю А' завжди можливо, оскільки початкова мережа представляється кінцевим графом. Число етапів, необхідних для перетворення матриці, визначається максимальним значенням рангу у всіх найкоротших шляхах від вершини-витоку до решти вершин мережі. Максимально можливе число етапів, необхідних для перетворення матриці А, матиме місце у разі представлення мережі графом-деревом з двома кінцевими вершинами і складе (n - 1) для графа з n вершин.

«Етапом» назвемо процес вибору з вершин графа вершин, суміжних вже вибраним, тобто що мають з вибраними безпосередній зв'язок. Так, перший етап полягає у виборі вершин, суміжних вершині-витоку, другий - у виборі всіх вершин, суміжних вибраним на першому етапі, і так далі, до тих пір, поки всі вершини графа не будуть вибрані.

Початковими для роботи алгоритму є: матриця А і три допоміжні двійкові слова довжиню n - накопичення Н, гасіння Г і ознаки закінчення формування матриці А' - ПФ.

Алгоритм полягає у виконанні кроків:

Крок 1. Запис початкового стану Г - нуль в розряді з номером вершини-витоку, одиниці - у всій решті розрядів.

Крок 2. Запис рядка вершини-витоку i з матриці А в матрицю А', в Н і ПФ.

Крок 3. Логічне множення інверсії Н і Г, результат залишається в Г: Г = /\ Г. Запис нулів у всі розряди Н.

Крок 4. Визначення номера чергової вершини k відповідно до вмісту одиниці в k -му розряді ПФ.

Крок 5. Логічне множення k -го рядка матриці А і Г, результат поміщається в k -й рядок матриці А': А'k = Ak /\ Г.

Крок 6. Логічне складання k-го рядка матриці А' і Н, результат поміщається в Н:

Н = А'k V Н.

Рисунок 2.9 – Зображення мережі матриці табл. 2.13

Крок 7. Перевірка проглядання всіх рядків матриці А відповідно до змісту ПФ. Перехід до кроку 8 при закінченні перегляду, інакше - повернення до кроку 4.

Крок 8. Запис вмісту Н в ПФ:Н→ ПФ.

Крок 9. Перевірка закінчення формування матриці А'. Якщо ПФ = 0, кінець алгоритму, інакше - повернення до кроку 3.

Для мережі, зображеної на малюнку 2.9, матриця А = [а ij] представлена в табл. 2.13.

 

Таблиця 2.13 – Матриця А = [а ij]

 

1 2 3 4 5 6

 

У матриці А елементи головної діагоналі а = 0.

Після першого етапу для вершини-витоку 1 в результаті перетворення рядків 2 і 3, відповідним вершинам, суміжним вершині-витоку 1, матриця А' матиме вид таблиці 2.14. Результуюча матриця А' представлена в табл. 2.15. Для пошуку по матриці А' найкоротших шляхів необхідно виконати наступні дії.

Нехай визначається шлях в деяку вершину j - µij .

Таблиця 2.14 – Матриця А'

1 2 3 4 5 6

 

Таблиця 2.15 – Результуюча матриця А'

1 2 3 4 5 6

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

Так, по матриці А' одержимо наступні шляхи мінімального рангу з вершини 1 у всю решту вершин графа: 1 – 2; 1 – 3; 1 – 3 – 4 ; 1 – 2 – 5, 1 – 3 – 5; 1 – 3 – 4 – 6, 1 – 2 – 5 – 6, 1 – 3 – 5 – 6.

 

2.2.2. Мережеві алгоритми пошуку найкоротших шляхів

Задача пошуку найкоротшого шляху (шляхи мінімальної вартості) з деякого витоку s в деякий стік t може бути сформульована як задача лінійного програмування (ЛП).

Вважатимемо, як і раніше, що кожному ребру (i, j) графа поставлено у відповідність деяке число сij зване узагальненою вартістю ребра (в якості цієї вартості може використовуватися і значення lij - довжини ребра, tij - часу передачі інформації по ребру і т. д.). Фіктивним, або «безкоштовним» ребрам приписується вартість сij = 0, а кожній парі вершин (i, j), що не мають прямого зв'язку, - вартість сij =∞.

Задача знаходження найкоротшого шляху з витоку s в стік t є задача знаходження в заданому графі такого шляху, для якого вартість проходження одиниці потоку мінімальна.

Математично ця задача може бути записана як наступна задача ЛП:

мінімізувати

(2.9)

При умові, що

(2.10)

(2.11)

(2.12)

Тут fij -величина потоку, що протікає по ребру (i, j).

Згідно рівності (2.10), одиниця потоку витікає з витоку (тут j - суміжні з витоком s вершини).

Рівність (2.11) гарантує збереження даної одиниці потоку при протіканні по графу ( (i, j) - будь-яке ребро графа).

Згідно рівності (2.12), одиниця потоку втікає в стік t (тут j - суміжні стоку t вершини).

Як найкоротший шлях може бути узята послідовність суміжних ребер (i, j), для яких fij = 1.

Для вирішення поставленої задачі був розроблений спеціальний метод, відомий під назвою алгоритму Дейкстри [1, 8, 11].

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

Кожній вершині, в яку не можна потрапити безпосередньо з витоку, приписується тимчасова позначка ∞, а всій решті вершин - тимчасові позначки csj, j ≠ s. Якщо визначено, що вершина належить найкоротшому шляху, її позначка стає постійною. Алгоритм заснований на простому твердженні: частина найкоротшого шляху є найкоротший шлях.

Алгоритм починає працювати при j = s . Потім величина j послідовно збільшується на одиницю і при j = t алгоритм завершує роботу.

Для заданої вершини j через L j позначатимемо оцінку довжини найкоротшого шляху з витоку s у вершину j. Якщо ця оцінка не може бути поліпшена, то відповідне значення назвемо постійною позначкою і позначатимемо , інакше вершина має тимчасову позначку.

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

1. Розглянути вершини, що залишилися, з тимчасовою позначкою. Порівняти величину кожної тимчасової позначки з сумою величини останньої з постійних позначок і довжини ребра, що веде з відповідної постійно поміченої вершини в дану вершину. Мінімальна з двох порівнюваних величин визначається як нова тимчасова позначка даної вершини. Відзначимо, що якщо величина старої тимчасової позначки менше за другу з порівнюваних величин, то позначка залишається колишньою.

2. Серед тимчасових позначок вибрати ту, значення якої мінімальне, і оголосити її постійною позначкою. Якщо при цьому постійна позначка приписується вершині t , то алгоритм завершує роботу. Інакше перейти на крок 1.

Алгоритм може бути виконаний за допомогою таблиці рішення, в якій стовпці відповідають вершинам графа, рядки - крокам обчислювального процесу, а її елементи - постійним і тимчасовим позначкам.

 

Рисунок 2.10 – Зображення графа

Розглянемо граф, зображений на мал. 2.10. Вершина s тут є витоком, t-стоком, а числа сij , приписані ребрам, відповідають їх довжині, або вартості, або часу і т.д.

Робота алгоритму починається з того, що витоку s приписується постійна позначка 0п, а вершинам 1, 2, .., t - тимчасові позначки Lj = csj. Дані позначки записуються в таблицю 2.16 як нульовий крок.

 

Таблиця 2.16 – Значення позначок

  Крок Вершина
s t

У таблиці 2.16 на кроці 0 L1 = 0, оскільки довжина ребра cs1 = 0, решта вершин має позначки ∞, оскільки вони не мають безпосереднього зв'язку з вершиною s.

На кроці 1 вершина 1 одержує постійну позначку, оскільки L1= 0 є мінімальною серед всіх тимчасових позначок.

Вершини 2 і 3 безпосередньо пов'язані з вершиною 1, останньої з постійно помічених вершин. Для них:

L2 = L1 + с12 = 0 + 3 < ∞ і L3 = L1 + с13 = 0 + 7 < ∞.

Тому вершинам 2 і 3 приписуються нові тимчасові позначки L2 = 3 і L3 = 7.

Далі на кроці 2 вершина 2 одержує постійну позначку 3п ,від неї змінюються тимчасові позначки вершин 3 і 6, а саме:

 

L3 = L2+ с23 = 3 + 2 = 5 < 7,

L6 = L2 + с26 = 3 + 1= 4<∞.

В результаті L3 = 7, L6 = 4.

На кроці 3 постійну позначку одержує вершина 6 – 4п і т.д.

В результаті виконання сьомого кроку вершині t приписується постійна позначка L8 = 7п. Отже, довжина найкоротшого шляху з s в t дорівнює 7. Цей шлях складається з ребер (i, j), для кожного з яких різниця між значеннями постійних позначок його кінцевих вершин i і j рівна довжині цього ребра. Тобто умова, при якій вершини i і j належать найкоротшому шляху, може бути записано:

 

Lj = Lі + сij (2.13)

Співвідношення (2.13) можна використовувати рекурсивно, рухаючись від вершини t до вершини s. В



Последнее изменение этой страницы: 2016-06-10

headinsider.info. Все права принадлежат авторам данных материалов.