Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Підсумкове завдання 1
Приклад 1 Маємо орієнтований граф, де задані ваги дуг. Знайдемо найкоротший шлях у графі від вершини до вершини методом Дейкстри. 1) d 1=0, di =∞, де i = 2, 3, 4, 5, 6; 2) = => dy = 0, d 2 = min(∞, 0+4) = 4, d 3 = min(∞, 0+2) = , d 4 = min(∞, 0+7) = 7, d 5 = min(∞, 0+∞) = ∞, d 6 = min(∞, 0+∞) = ∞. Зауважимо, що cyx =0, якщо немає шляху (дуги) y→ x. Вибираємо мінімальну позначку, це d 3 = 2; 3) = => dy = 2, d 2 = min(4, 2+∞) = , d 4 = min(7, 2+∞) = 7, d 5 = min(∞, 2+3) = 5, d 6 = min(∞, 2+∞) = ∞; 4) = => dy = 4, d 4 = min(7, 4+3) = 7, d 5 = min(5, 4+2) = , d 6 = min(∞, 4+∞) = ∞; 5) = => dy = 5, d 4 = , d 6 = min(∞, 5+2) = 7; 6) = => dy = 7, d 6 = min(7, 7+2) = 7. Всі вершини мають остаточні позначки. При розв’язанні слід відразу на графі позначити остаточні позначки вершин. Таким чином найкращий шлях з початкової вершини до кінцевої вершини дорівнює 7. Також ми маємо найкоротший шлях з початкової вершини до будь-якої вершини графа. На графі слід також позначити цей найкоротший шлях. Приклад 2 Розглянемо приклад мережевого графа. Знайдемо для цієї мережі найкоротший шлях методом позначок, для якого використаємо формулу , де dj – позначка j-ої вершини, cij – вага дуги (i, j). Вершини, що остаточно позначені, об’єднаємо в множину I*. Вершини, сусідні з позначеними, об’єднаємо в множину ω (I*). В сусідні вершини включаються ті вершини, для яких існує хоча б одна дуга, що йде з позначеної вершини. I. d 1 = 0 (за формулою). Тобто вершина остаточно позначена і має позначку . На цьому етапі I* = {1}, ω (I*) = {2, 3, 4} – множина вершин, сусідніх з позначеними. Знайдемо тимчасові позначки вершин множини ω (I*) за формулою . d 2 = 0+2 = 2, d 3 = 0+1 = 1, d 4 = 0+4 = 4. З усіх тимчасових позначок вибираємо найменшу: . Таким чином, вершина одержує остаточну позначку . II. I* = {1, 3}, ω (I*) = {2, 4, 5, 6}. d 2 = 0+2 = 2, d 4 = min(0+4, 1+2) = 3, d 5 = 1+5 = 6, d 6 = 1+6 = 7. – вершина одержує остаточну позначку . III. I* = {1, 2, 3}, ω (I*) = {4, 5, 6, 7}. d 4 = min(2+3, 0+4, 1+2) = 3, d 5 = min(2+4, 1+5) = 6, d 6 = 1+6 = 7, d 7 = 2+6 = 8. – остаточно позначається вершина позначкою . IV. I* = {1, 2, 3, 4}, ω (I*) = {5, 6, 7}. d 5 = min(1+5, 3+1, 2+4) = 4, d 6 = 1+6 = 7, d 7 = 2+6 = 8. – остаточно позначається вершина позначкою . V. I* = {1, 2, 3, 4, 5}, ω (I*) = {6, 7, 8}. d 6 = min(1+6, 4+1) = 5, d 7 = min(2+6, 4+3) = 7, d 8 = 4+5 = 9. – остаточно позначається вершина позначкою . VI. I* = {1, 2, 3, 4, 5, 6}, ω (I*) = {7, 8}. d 7 = min(2+6, 4+3) = 7, d 8 = min(5+2, 4+5) = 7. – остаточно позначається вершина позначкою . Ми одержали дві однакові позначки. В цьому випадку остаточно позначаємо вершину з меншим номером. VII. I* = {1, 2, 3, 4, 5, 6, 7}, ω (I*) = {8}. d 8 = min(7+4, 5+2, 4+5) = 7. Остаточно позначимо вершину позначкою . Таким чином, довжина найкоротшого шляху в графі дорівнює 7. Зобразимо граф з позначками і покажемо найкоротший шлях з вершини до вершини . Найкоротший шлях в графі: . Приклад 3 Знайти найдовший шлях у графі. Вершини, що остаточно позначені, об’єднаємо в множину I*. Вершини, сусідні з позначеними, об’єднаємо в множину ω (I*). Тут в сусідні включаються ті вершини, для яких всі дуги йдуть з остаточно позначених вершин. d 1 = 0 – остаточно позначена вершина позначкою . I. I* = {1}, ω (I*) = {2, 3}. d 2 = 0+2 = 2, d 3 = 0+1 = 1. – остаточно позначається вершина позначкою . II. I* = {1, 2}, ω (I*) = {3}. d 3 = 0+1 = 1. Остаточно позначається вершина позначкою . III. I* = {1, 2, 3}, ω (I*) = {4}. d 4 = max(0+4, 2+3, 1+2) = 5. Остаточно позначається вершина позначкою . IV. I* = {1, 2, 3, 4}, ω (I*) = {5}. d 5 = max(2+4, 5+1, 1+5) = 6. Остаточно позначається вершина позначкою . V. I* = {1, 2, 3, 4, 5}, ω (I*) = {6, 7}. d 6 = max(1+6, 6+1) = 7, d 7 = max(2+6, 6+3) = 9. Остаточно позначається вершина позначкою . VI. I* = {1, 2, 3, 4, 5, 7}, ω (I*) = {6}. d 6 = max(1+6, 6+1) = 7, Остаточно позначається вершина позначкою . VII. I* = {1, 2, 3, 4, 5, 6, 7}, ω (I*) = {8}. d 6 = max(9+4, 6+5, 7+2) = 13. Вершина остаточно позначається позначкою . Це і є довжина найдовшого шляху в графі. Зобразимо цей шлях і позначимо вершини. Найдовший шлях у графі Довжина цього шляху дорівнює 13.
|