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

 

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

 

О з н а ч е н н я. Шляхом називається послідовність вершин µ_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. Робота алгоритму зреалізовується за допомогою розставляння у вершин позначок виду (L_sj, i), де L_sj – довжина найкоротшого шляху з вихідної вершини s в певну вершину j, а i – попередня j вершина в цьому шляху.

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

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

Крок 0. Для вершини s покладається L_ss = 0, а для інших вершин L_sj = ∞. Всі вершини мають тимчасові позначки виду (L_sj,s).

Крок 1. Серед вершин з тимчасовими позначками вибираємо вершину r, для котрої L_sr=min(L_sj). Позначка вершини r стає постійною.

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

Крок 3. Перераховуємо тимчасові позначки для вершин, суміжних до вершини r, що дістала постійну позначку на кроці 1, відповідно до виразу:

L_sj=min(L_sj, L_sr+L_rj ).

Перехід до кроку 1.

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

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

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

Крок 0. Позначка P для вершини s має вид: Р_s=(0, 0). Для решти вершин Рi=(∞, s). Всі позначки тимчасові.

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

Крок 3. Перераховуємо тимчасові позначки для вершин, суміжних до вершини s. Для вершини 1 параметр довжини

L_s1 = L_ss + l_s1 = 0 + 15 = 15.

Дістане значення менше за те, що є (L_si = ∞) і тому нове значення тимчасової позначки буде P₁ = (15, s).

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

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

P₂ =(17, s) можна залишити без зміни, оскільки новий параметр довжини дорівнює попередньому значенню.

P₅ =(22, 3),

P_t =(30, 3).

Вершина 1 на кроці 1 дістає постійну позначку, оскільки її параметр довжини мінімальний. Нове значення позначки на кроці 3 дістає вершина 4, а саме P₄ = (24, 1).

 

Рисунок 2.9

 

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

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

На цьому робота алгоритму закінчується.

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