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

В попередній роботі розглянуто алгоритм, що дозволяє знайти найкоротші шляхи з першого вузла мережі до решти вузлів. Розглянемо задачу знаходження найкоротших ланцюгів між усіма парами вузлів мережі G=(N, A) (задачу про багатополюсний найкоротший ланцюг). Отже, N={1, 2,..., n} – множина вузлів мережі. Дуги з множини А можуть бути орієнтованими або неорієнтованими. Однак, оскільки напрямок потоку в неорієнтованих дугах неможливо визначити заздалегідь, то кожну таку дугу слід замінити двома орієнтованими дугами з протилежними напрямками та довжиною, що дорівнює довжині неорієнтованої дуги.

Якщо довжині кожної дуги відповідає відстань або вартість одиниці потоку по цій дузі С_ij, то найкоротшим ланцюгом між двома довільними вузлами є ланцюг, вартість одиниці потоку для якого є мінімальною.

Позначимо через d*_ik довжину найкоротшого ланцюга з вузла i до вузла k.

Припустимо, що величина d_ik представляє найкращу оцінку довжини найкоротшого ланцюга, що з’єднує вузли i й k. Тоді довжина = d_ij+d_jk кожного найкоротшого ланцюга, що проходить через проміжний вузол j, або перевищує величину d_ik, або поточна довжина найкоротшого ланцюга дорівнює . Однак якщо довжина нового ланцюга (через деякий транзитний вузол) менше d_ik, то поточне значення d_ik слід замінити на .

Алгоритм Флойда [3] працює наступним чином. Спочатку за довжину найкоротшого ланцюга між двома довільними вузлами i та k приймається величина довжини дуги (i, k), що з’єднує ці вузли (рис. 2.1). Потім послідовно перевіряються всі можливі транзитні вузли, що розташовані між i та k. Якщо довжина ланцюга, що проходить через деякий транзитний вузол, менше поточного значення d_ik, то оцінці d_ik привласнюється нове значення. Ця процедура повторюється для всіх можливих пар вузлів, доки не будуть отримані всі значення d*_ik.

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

d_ij + d_jk ≥ d_ik i≠ j≠ k, (2.1)

оскільки в протилежному випадку найкоротший ланцюг и вузла i в k повинен містити вузол j і тоді величина d_ik не дорівнювала б довжині найкоротшого ланцюга. В алгоритмі Флойда початковим значенням d_ik є величина С_ik, а потім ця оцінка послідовно покращується, доки не буде знайдено найкоротший ланцюг між вузлами i та k.

Алгоритм Флойда дозволяє вирішити задачу побудови багатополюсного найкоротшого ланцюга для мережі з n вузлів за n ітерацій. Для формального описання ітеративної процедури пошуку рішення, позначимо символом d^j_ik оцінку довжини найкоротшого ланцюга з вузла i до вузла k, отриману на j - й ітерації. Ця оцінка обирається як найменше значення з оцінки цього ланцюга на попередній (j-1) - й ітерації та довжини ланцюга через транзитний вузол j:

d_ik ^j= min [d_ik ^j-1; d_ij ^j-1+d_jk ^j-1], i ≠ j ≠ k (2.2)

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

Будемо використовувати матричний метод, який дозволить запам’ятовувати довжини найкоротших ланцюгів та їх маршрути. На кожній ітерації алгоритму будуються дві матриці. Перша – матриця довжин – містить поточні оцінки довжини найкоротших ланцюгів, тобто на j-й ітерації ця матриця виглядає:

D^j =[d^j_ik].

Алгоритм починає роботу при Dº =[d°_ik], де d°_ik=C_ik. Потім виконується порівняння (2.2) для усіх елементів матриці D° і обчислюється D¹ і т. д. доки для кожної пари вузлів не буде виконано критерій оптимальності (2.1).

Друга матриця – матриця маршрутів – необхідна для находження транзитних вузлів найкоротших ланцюгів. На j - й ітерації вона визначається як R^j=r^j_ik, где r^j_ik — перший транзитний вузол найкоротшого ланцюга з i в k, що обирається серед вузлів множини {1, 2,..., j} (i ≠ j ≠ k). На початку алгоритма R°=[r°_ik], где r°_ik=k. На j-й ітерації вузол r^j_ik обирається з наступного співвідношення:

(2.3)

Таким чином, після побудови початкових матриць D° и R ° треба для кожного j =1, 2,..., n, виконати 2 кроки:

Крок 1. Визначити j-й вузол як базовий. (Тобто на цій ітерації саме цей вузол перевіряється як «кандидат» в транзитні вузли між іншими вузлами). Викреслити j-й рядок та j-й стовпчик матриці відстаней D^j-1, а також рядки і стовпчики D^j-1, що містять в базовому рядку чи стовпчику елементи, рівні ¥.

Крок 2. Кожний невикреслений елемент d_ik^j-1 (k≠ j) матриці відстаней порівнюється з сумою d_ij ^j-1 та d_jk ^j-1 елементів, розташованих на перетині розглянутого стовпчика і базового рядка та розглянутого рядка і базового стовпчика відповідно.

Якщо виконується нерівність d_ij^j-1+d_jk ^j-1 ≥ d_ik ^j-1, тобто шлях через транзитний вузол j гірше, ніж попередня оцінка, то перейти до розгляду наступного невикресленого елемента. В протилежному випадку включення вузла j в маршрут зменшує довжину найкоротшого ланцюга з вузла i до вузла k, отже необхідно поновити значення відповідних елементів в обох матрицях:

елементу d_ik^j-1 матриці довжин присвоїти значення d_ik^j=d_ij^j-1+d_jk^j-1, а відповідному елементу матриці маршрутів — значення j. Після перегляду усіх елементів знову перейти до кроку 1 при j=j+l. При j=n будуть побудовані матриця відстаней і матриця маршрутів, що надають рішення задачі.

Приклад 2.

Рисунок 2.2 – Граф мережі

Задано граф мережі (рис. 2.2), в якій потрібно знайти найкоротші шляхи між усіма парами вузлів.

Для рішення даної задачі потрібно на кожному кроці складати матриці найкоротших відстаней (D) і матриці маршрутів (R). Матриці відстаней фіксують зміни довжин маршрутів, а матриця маршрутів останній вузол, через який проходить найкоротший шлях.

Початкові значення матриць: D⁰ – матриця відстаней (вартостей) С_ij (якщо немає прямого зв'язку, то ставиться «∞»), і R⁰ – матриця, де в кожнім стовпці проставлено номер цього стовпця.

Крок № 0: j=0

D⁰

R⁰

Крок № 1: j=1.

З матриці D⁰ викреслюємо ті рядки і стовпці, де на перетинанні з першим стовпцем і першим рядком присутня «∞», тобто стовпці 3, 5, 6, 7, 8 і рядки 3, 5, 6, 7, 8.

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

d¹24 = min [d⁰24; d⁰21+d⁰14] = min[∞; 9+3] = 12,

d¹42 = min [d⁰42; d⁰41+d⁰12] = min[∞; 3+9] = 12,

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

D¹

R¹

Крок № 2: j=2.

Викреслюємо стовпці 6, 7, 8 і рядки 6, 7, 8.

d²13 = min [d¹13; d¹12+d¹23] = min [∞; 9+2] = 11,

d²15 = min [d¹15; d¹12+d¹25] = min [∞; 9+7] = 16,

d²31 = min [d¹31; d¹32+d¹21] = min [∞; 2+9] = 11,

d²45 = min [d¹45; d¹42+d¹25] = min [∞; 12+7] = 19,

d²51 = min [d¹51; d¹52+d¹21] = min [∞; 7+9] = 16,

d²54 = min [d¹54; d¹52+d¹24] = min [∞; 7+12] = 19,

Усі зміни вносимо в матриці.

D²

R²

Кроки №№ 3-8: j = 3, …, 8...

З 6 ітерації матриця D не міняється, отже, D⁵ і R⁵ – оптимальні.

D⁵

R⁵

Після одержання оптимальних матриць відстаней і маршрутів можна визначити найкоротшу відстань з одного вузла в інший і відповідний маршрут. Приміром, потрібно знайти найкоротший шлях між вузлами 1-5. По матриці D⁵ знаходиться найкоротша відстань: D₁₅⁵ = 9. По матриці R⁵ знаходиться маршрут проходження: в комірці 1-5 значення 4 (R₁₅⁵ = 4), тобто наступним після 1-го вузла буде 4-й, далі потрібно подивитися комірку 4-5 (R₄₅⁵ = 3), тобто після 4-го вузла йде 3-й.

Далі R₃₅⁵ = 5. У підсумку виходить маршрут: 1-4-3-5.