ываап Практична робота № 2 з дослідження операцій в транспортних системах студентки групи МП 2-2 Маркиної Ельзи Номер у журналі академічної групи - 9 Номер залікової книжки – 49092 Розглянемо задачу пошуку найкоротшого маршруту (шляху) на графі (у сенсі найкоротшої відстані). Задано граф G, у якому кожному ребру приписана позитивна вага. Граф – математична структура, яка складається з вершин графу і ребер (дуг), які об’єднують цей граф у єдине ціле. Довжина шляху в такій постановці дорівнює сумі довжин ребер, що складають цей шлях. Задача зводиться до пошуку найкоротшого шляху між двома заданими вершинами графа G. Нехай є орієнтований граф G: G = (V; Е), у якого всі дуги мають позитивні вартості, а одна вершина визначена як джерело. Завдання полягає у пошуку вартості найкоротших шляхів від джерела до усіх інших вершин графа G. Представимо граф G у вигляді карти рейсових маршрутів з одного міста у інший, де кожна вершина відповідає місту, а друга V → W – рейсовому маршруту з міста V до міста W. Таким чином мітка дуги V → W – це час переїзду з міста V у місто W. При цьому може виникнути припущення, що в даному випадку у якості моделі більше підходить неорієнтований граф, оскільки мітки дуг V → W і W → V можуть збігатися, але допущення про збіг цих міток принципово не впливає на рішення поставленої задачі. Таким чином, для рішення поставленої задачі будемо використовувати алгоритм Деікстри. Накреслимо наш неорієнтований граф: Цей алгоритм будує множину вершин S для яких найкоротші шляхи від джерела (вершина А 1 (1)) уже відомі. На кожному кроці до множини S додається та з вершин, яка залишилась, відстань до якої від джерела менша , ніж від інших вершин, що залишились. Якщо вартості всіх дуг – позитивні, то можна бути упевненим, що найкоротший шлях (маршрут) від джерела до вершини проходить тільки через вершини множини S. Назвемо такий шлях особливим. На кожному кроці алгоритму (методу) використовується масив D, у який записуються довжини найкоротших особливих шляхів до кожної вершини. Коли множина S буде містити усі вершини графа G, тобто для усіх вершин будуть знайдені особливі шляхи, тоді масив D буде містити довжини найкоротших шляхів від джерела до кожної вершини. С – двовимірний масив, який містить вартості перевезення одиниці вантажу між усіма транспортними вузлами ДТМ. 1 2 3 4 5 6 7
1 2 3 С= 45 6 7 Для опрацювання блок-схеми алгоритму побудуємо наступну таблицю:
𝐃[𝐕] = 𝐦𝐢𝐧(𝐃[𝐕],𝐃[𝐖]+ 𝐂[𝐖,𝐕]) (𝐃[𝐖]+ 𝐂[𝐖,𝐕]) < 𝐃[𝐕] Крок 1: V=3: D [3] = min (D [3], D [2]+C [2,3]) = min(5,1+4) = 5 (D[2] + C[2,3]) < D[3] 1 + 4 < 5 - умова не виконується V=4: D [4] = min (D [4], D[2]+C[2,4]) = min(4,1+∞) = 4 (D[2] + C[2,4]) < D[4] 1 + ∞ < 4 - умова не виконується V=5: D[5] = min(D[5],D[2]+C[2,5]) = min(6,1+∞) = 6 (D[2] + C[2,5]) < D[5] 1 + ∞ < 6 – умова не виконується V=6: D[6] = min(D[6],D[2]+C[2,6]) = min(∞,1+2) = 3 (D[2] + C[2,6]) < D[6] 1 + 2 < ∞ - умова виконується P[V] = W P[6] = 2 V=7: D[7] = min(D[7],D[2]+C[2,7]) = min(∞,1+2) = 3 (D[2] + C[2,7]) < D[7] 1 + 2 < ∞ - умова виконується P[V] = W P[7] = 2 Крок 2 V=3: D[3] = min(D[3],D[6]+C[6,3]) = min(5, ∞+∞) = 5 (D[6] + C[6,3]) < D[3] ∞ + ∞ < 5 - умова не виконується V=4: D[4] = min(D[4],D[6]+C[6,4]) = min(4, ∞+∞) = 4 (D[6] + C[6,4]) < D[4] ∞ + ∞ < 4 - умова не виконується V=5: D[5] = min(D[5],D[6]+C[6,5]) = min(6, ∞+6) = 6 (D[6] + C[6,5]) < D[5] ∞ + 6 < 6 - умова не виконується V=7: D[7] = min(D[7],D[6]+C[6,7]) = min(∞,∞+2) =∞ (D[6] + C[6,7]) < D[7] ∞ + 2 < ∞ - умова не виконується Крок 3 V=3: D[3] = min(D[3],D[4]+C[4,3]) = min(5,4+3) = 5 (D[4] + C[4,3]) < D[3] 4 + 3 < 5 - умова не виконується V=5: D[5] = min(D[5],D[4]+C[4,5]) = min(6,4+5) = 6 (D[4] + C[4,5]) < D[5] 4 + 5 < 6 - умова не виконується V=7: D[7] = min(D[7],D[4]+C[4,7]) = min(∞,4+3) = 7 (D[4] + C[4,7]) < D[7] 4 + 3 < ∞ - умова виконується P[V] = W P[7] = 4 Крок 4 V=3: D[3] = min(D[3],D[5]+C[5,3]) = min(5,6+∞) = 5 (D[5] + C[5,3]) < D[3] 6 + ∞ < 5 - умова не виконується V=7: D[7] = min(D[7],D[5]+C[5,7]) = min(∞,6+∞) = ∞ (D[5] + C[5,7]) < D[7] 6 + ∞ < ∞ - умова не виконується Крок 5 V=7: D[7] = min(D[7],D[3]+C[3,7]) = min(∞,5+2) = 7 (D[3] + C[4,7]) < D[7] 5 + 2 < ∞ - умова виконується P[V] = W P[7] = 3 Побудуємо найкоротші маршрути від третьої вершини (джерела), до вершин, які залишились (1, 2, 4, 5, 6, 7): 1 → 2 = 1 1 → 3 = 5 1 → 4 = 4 1 → 5 = 6 1 → 2 → 6 = 3 1 → 2 → 7 = 3
Крок 1: V=3: D[3] = min(D[3],D[1]+C[1,3]) = min(4,1+5) = 4 (D[1] + C[1,3]) < D[3] 1 + 5 < 4 – умова не виконується V=4: D[4] = min(D[4],D[1]+C[1,4]) = min(∞,1+4) = 5 (D[1] + C[1,4]) < D[4] 1 + 4 < ∞ – умова виконується P[V] = W P[4] = 1 V=5: D[5] = min(D[5],D[1]+C[1,5]) = min(∞,1+6) = 7 (D[1] + C[1,5]) < D[5] 1 + 6 < ∞ – умова виконується P[V] = W P[5] = 1 V=6: D[6] = min(D[6],D[1]+C[1,6]) = min(2,1+∞) = 2 (D[1] + C[1,6]) < D[6] 1 + ∞ < 2 – умова не виконується V=7: D[7] = min(D[7],D[1]+C[1,7]) = min(2,1+∞) = 2 (D[1] + C[1,7]) < D[7] + ∞ < 2 – умова не виконується Крок 2: V=3: D[3] = min(D[3],D[6]+C[6,3]) = min(4,2+∞) = 4 (D[6] + C[6,3]) < D[3] + ∞ < 4 – умова не виконується V=4: D[4] = min(D[4],D[6]+C[6,4]) = min(∞,2+∞) = ∞ (D[6] + C[6,4]) < D[4] 2 + ∞ < ∞ – умова не виконується V=5: D[5] = min(D[5],D[6]+C[6,5]) = min(∞,2+6) = 8 (D[6] + C[6,5]) < D[5] 2 + 6 < ∞ – умова виконується P[V] = W P[5] = 6 V=7: D[7] = min(D[7],D[6]+C[6,7]) = min(2,2+2) = 2 (D[6] + C[6,7]) < D[7] 2 + 2 < 2 – умова не виконується Крок 3: V=3: D[3] = min(D[3],D[7]+C[7,3]) = min(4,2+2) = 4 (D[7] + C[7,3]) < D[3] 2 + 2 < 4 – умова не виконується V=4: D[4] = min(D[4],D[7]+C[7,4]) = min(∞,2+3) = 5 (D[7] + C[7,4]) < D[4] 2 + 3 < ∞ – умова виконується P[V] = W P[4] = 7 V=5: D[5] = min(D[5],D[7]+C[7,5]) = min(∞,2+∞) = ∞ (D[7] + C[7,5]) < D[5] 2 + ∞ < ∞ – умова не виконується Крок 4: V=4: D[4] = min(D[4],D[3]+C[3,4]) = min(∞,4+3) = 7 (D[3] + C[3,4]) < D[4] 4 + 3 < ∞ – умова виконується P[V] = W P[4] = 3 V=5: D[5] = min(D[5],D[3]+C[3,5]) = min(∞,4+∞) = ∞ (D[3] + C[3,5]) < D[5] 4 + ∞ < ∞ – умова не виконується Крок 5: V=5: D[5] = min(D[5],D[4]+C[4,5]) = min(∞,∞+5) = ∞ (D[4] + C[4,5]) < D[5] ∞ + 5 < ∞ – умова не виконується Побудуємо найкоротші маршрути від другої вершини (джерела), до вершин, які залишились (1, 3, 4, 5, 6, 7): 2 → 1 = 1 2 → 3 = 4 2 → 1 → 4 = 5 2 → 1 → 5 = 7 2 → 6 = 2 2 → 7 = 2
Крок 1: V=1: D[1] = min(D[1],D[7]+C[7,1]) = min(5,2+∞) = 5 (D[7] + C[7,1]) < D[1] 2 + ∞ < 5 – умова не виконується V=2: D[2] = min(D[2],D[7]+C[7,2]) = min(4,2+2) = 4 (D[7] + C[7,2]) < D[2] 2 + 2 < 4 – умова не виконується V=4: D[4] = min(D[4],D[7]+C[7,4]) = min(3,2+3) = 3 (D[7] + C[7,4]) < D[4] 2 + 3 < 3 – умова не виконується V=5: D[5] = min(D[5],D[7]+C[7,5]) = min(∞,2+∞) = ∞ (D[7] + C[7,5]) < D[5] 2 + ∞ < ∞ – умова не виконується V=6: D[6] = min(D[6],D[7]+C[7,6]) = min(∞,2+2) = 4 (D[7] + C[7,6]) < D[6] + 2 < ∞ – умова виконується P[V] = W P[6] = 7 Крок 2: V=1: D[1] = min(D[1],D[4]+C[4,1]) = min(5,3+4) = 5 (D[4] + C[4,1]) < D[1] + 4 < 5 – умова не виконується V=2: D[2] = min(D[2],D[4]+C[4,2]) = min(4,3+∞) = 4 (D[4] + C[4,2]) < D[2] 3 + ∞ < 4 – умова не виконується V=5: D[5] = min(D[5],D[4]+C[4,5]) = min(∞,3+5) = 8 (D[4] + C[4,5]) < D[5] 3 + 5 < ∞ – умова виконується P[V] = W P[5] = 4 V=6: D[6] = min(D[6],D[4]+C[4,6]) = min(∞,3+∞) = ∞ (D[4] + C[4,6]) < D[6] + ∞ < ∞ – умова не виконується Крок 3: V=1: D[1] = min(D[1],D[2]+C[2,1]) = min(5,4+1) = 5 (D[2] + C[2,1]) < D[1] + 1 < 5 – умова не виконується V=5: D[5] = min(D[5],D[2]+C[2,5]) = min(∞,4+∞) = ∞ (D[2] + C[2,5]) < D[5] 4 + ∞ < ∞ – умова не виконується V=6: D[6] = min(D[6],D[2]+C[2,6]) = min(∞,4+2) = 6 (D[2] + C[2,6]) < D[6] + 2 < ∞ – умова виконується P[V] = W P[6] = 2 Крок 4: V=5: D[5] = min(D[5],D[1]+C[1,5]) = min(∞,5+6) = 11 (D[1] + C[1,5]) < D[5] + 6 < ∞ – умова виконується P[V] = W P[5] = 1 V=6: D[6] = min(D[6],D[1]+C[1,6]) = min(∞,5+∞) = ∞ (D[1] + C[1,6]) < D[6] 5 + ∞ < ∞ – умова не виконується Крок 5: V=6: D[6] = min(D[6],D[5]+C[5,6]) = min(∞,∞+6) = ∞ (D[5] + C[5,6]) < D[6] ∞ + 6 < ∞ – умова не виконується Побудуємо найкоротші маршрути від третьої вершини (джерела), до вершин, які залишились (1, 2, 4, 5, 6, 7): 3 → 1 = 5 3 → 2 = 4 3 → 4 = 3 3 → 1→ 5 = 11 3 → 7 → 6 = 4 3 → 7 = 2 |