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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



 

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

 

О з н а ч е н н я. Шляхом називається послідовність вершин µ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=min(Lsj ). Позначка вершини r стає постійною.

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

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

Lsj=min(Lsj, Lsr+Lrj ).

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

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

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

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

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

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

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

Ls1 = Lss+ls1 = 0 + 15 = 15.

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

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

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

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

P5=(22, 3),

Pt=(30, 3).

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

 

Рисунок 2.9

 

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

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

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

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

 



Последнее изменение этой страницы: 2016-04-23; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.226.244.254 (0.024 с.)