Знаходження найкоротшого шляху в зв'язувальній мережі

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

О з н а ч е н н я. Шляхом називають послідовність вершин µ ir = (i, j, …, r) або послідовність дуг (ребер) µ ir = {(i, j), …, (к, r)}, що з'єднують пару i та r вершин графа G.

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

Шлях з вершини i в вершину r, який має мінімально можливу довжину, є найкоротшим шляхом.

Задачу про знаходження найкоротшого шляху можна сформулювати в наступному вигляді.

Дано зв'язувальну мережу G, у якій кожній дузі (ребру) приписано вагу, пропорційну до її (його) довжини. Потрібно знайти шлях µ st між заданими вершинами s та t, який має мінімально можливу довжину, тобто

де М – множина всіх можливих шляхів з s до t.

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

Особливістю цього алгоритму є те, що в процесі його виконання одночасно будують найкоротші шляхи з заданої вершини s до усіх іншіх вершин мережі. Це пояснюється тим, що будь-яка вершина i ∈ N може виявитися проміжною на найкоротшому шляху з s до t. Після закінчення роботи алгоритму вершина s стає з’єднаною з усіма іншими вершинами зв'язувальної мережі G, зокрема і з вершиною t, найкоротшими шляхами, а дуги (ребра), які увійшли до них, утворюють деяку підмережу без циклів, тобто “дерево” з коренем у вершині s.

Робота алгоритму реалізується за допомогою розміщення у вершинах позначок (Lsj, i), де Lsj – довжина найкоротшого шляху з початкової вершини s до деякої вершини j, а i попередня до j – вершина на цьому шляху.

Позначки поділяють на тимчасові та постійні.

Тимчасові позначки можуть змінюватися в результаті роботи алгоритму, а постійні – не змінюються.

Нижче наводимо алгоритм Дейкстри покроково.

Крок 0. Для вершини s вважатиме, що Lss = 0, а для решти вершин Lsj = ∞. Усі вершини мають тимчасові позначки типу (Lsj, s).

Крок 1. Серед вершин з тимчасовими позначками вибираємо вершину r, для якої Lsr має найменше значення серед усіх Lsj. Таким чином позначка вершини r стає постійною.

Крок 2. Якщо всі вершини мережі отримали постійні позначки – кінець роботи алгоритму. Інакше – перехід до кроку 3.

Крок 3. Перераховуємо тимчасові позначки для вершин, суміжних з вершиною r, яка отримала постійну позначку на кроці 1, відповідно до формули Lsj = min(Lsj,Lsr + Lrj). Перехід до кроку 1.

Трасування шляху µ st здійснюється у зворотному напрямку, прямуючи з вершини t до s, керуючись вершинами i в постійних позначках.

Проілюструємо роботу алгоритму Дейкстри на прикладі.

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

Крок 0. Позначка P для вершини s має вигляд: Рs = (0,0).

Для інших вершин Рi = (∞,s). Усі позначки тимчасові.

Крок 1. Серед тимчасових позначок найменшу довжину має вершина s, так як Lss= 0. Її позначка стає постійною (позначимо її подвійними дужками).

Крок 2. Перераховуємо тимчасові позначки для вершин, суміжних з вершиною s. Для вершини 1 параметр довжини Ls1 = Lss + ls1 = 0 + 15 = 15.

Отримане значення є меншим від наявного (Lsi = ∞), а тому нове значення тимчасової позначки буде P1 = (15, s).

Для вершини 2 нова позначка має значення P2=(17, s).

Для вершини 3 – P3 = (10, s).

Перейшовши до кроку 1, вибираємо вершину 3, тому що вона має найменший параметр довжини Ls3 = 10 серед усіх вершин з тимчасовими позначками. Її позначка стає постійною. Оскільки ще не всі вершини отримали постійні позначки, переходимо до кроку 2 і здійснюємо перерахунок позначок для вершин, суміжних з вершиною 3.

P2 = (17, s) можна залишити без змін, тому що новий параметр довжини дорівнює попереднім значенням.

P5 = (22, 3).

Pt = (30, 3).

Вершина 1 на кроці 1 отримує постійну позначку, оскільки її параметр довжини є мінімальним.

Нове значення позначки на кроці 2 отримує вершина 4, а саме P4 = (24, 1).

Повертаючись до кроку 1, робимо постійну позначку на вершині 5. Змінити значення позначок на кроці 3 не вдається.

Фіксуємо наступну вершину з постійною позначкою – це вершина 4.

Змінити тимчасову позначку для вершини t не вдається, і вона автоматично стає постійною.

На цьому робота алгоритму закінчується. Довжина визначеного шляху µ st дорівнює 30 (перший параметр постійної позначки для вершини t). Трасування шляху визначаємо, рухаючись у зворотному напрямку від t до s через вершину, визначену як другий параметр постійної позначки. В даному випадку маємо: t→3→s.