Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Постановка задачі про найкоротший шлях в мережі



В мережі, що задається графом (I, U), де I – множина вершин, U – множина дуг з визначеною на ній функцією вартості cij ((i,j) –дуга з U), для фіксованих i1 та is знайти шлях

L = ((i1, i2),(i2, i3),...,(is-1, is))

з вершини i1 у вершину is, довжина якого

найменша.

Алгоритм методу Мiнтi. Методом Мiнтi розв’язується задача побудови дерева найкоротших шляхів в мережі з коренем у фіксованій вершині i1.

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

Нехай P r – множина вершин, позначених на кроцi r, а I r – множина вершин, позначених за r кроків.

Крок 0. Корiнь дерева (вершина i1) позначається сталою величиною h1= 0; i1 (h1)= i1 (0). Пiсля нульового кроку P 0 ={ i1 (0)}, I 0 ={ i1 (0)}.

Нехай виконано r кроків, при яких побудована множина

I r ={ i1 (0),..., ik (hk),...}

позначених вершин ik (hk), кожній з яких поставлене у відповідність число hk (чисельно рівне довжині найкоротшого шляху із вершини i1 у вершину ik).

Крок r +1. Будується переріз мережі, який породжується множиною позначених вершин I r i визначається множина J r ={..., im,...} непозначених вершин im мережі, в які заходять дуги перерізу. Для кожної дуги (ik, im) перерізу обчислюють суму hk + i позначають ті з дуг, для яких ця сума мінімальна. Потім, виділяють позначені дуги так, щоб в кожну непозначену вершину множини J r, в яку заходять позначені дуги перерізу, заходила б тільки одна виділена дуга. Пiсля виділення дуг позначають вершини – кінці виділених дуг. Величина позначки рівна мінімальній із сум hk + , обчислених для всіх дуг перерізу. Об’єднуючи множину I r з множиною P r+1 вершин, позначених на (r+1) – у кроцi, отримують множину I r+1 вершин, позначених за (r+1) кроків. Переходять до наступного кроку, якщо існує розріз, що породжується множиною I r+1.

Описаний процес продовжують до тих пір, поки можливе розширення множини позначених вершин. Якщо деяка вершина in мережі залишилась непозначеною після закінчення процедури Мiнтi, то шляху, що починається у вершині i1 i закінчується у вершині in, не існує.





Дата публикования: 2015-09-18; Прочитано: 339 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.149 с)...