Підсумкове завдання 1

Приклад 1 Маємо орієнтований граф, де задані ваги дуг.

Знайдемо найкоротший шлях у графі від вершини до вершини методом Дейкстри.

1) d ₁=0, d_i =∞, де i = 2, 3, 4, 5, 6;

2) = => d_y = 0,

d ₂ = min(∞, 0+4) = 4,

d ₃ = min(∞, 0+2) = ,

d ₄ = min(∞, 0+7) = 7,

d ₅ = min(∞, 0+∞) = ∞,

d ₆ = min(∞, 0+∞) = ∞.

Зауважимо, що c_yx =0, якщо немає шляху (дуги) y→ x. Вибираємо мінімальну позначку, це d ₃ = 2;

3) = => d_y = 2,

d ₂ = min(4, 2+∞) = ,

d ₄ = min(7, 2+∞) = 7,

d ₅ = min(∞, 2+3) = 5,

d ₆ = min(∞, 2+∞) = ∞;

4) = => d_y = 4,

d ₄ = min(7, 4+3) = 7,

d ₅ = min(5, 4+2) = ,

d ₆ = min(∞, 4+∞) = ∞;

5) = => d_y = 5,

d ₄ = ,

d ₆ = min(∞, 5+2) = 7;

6) = => d_y = 7,

d ₆ = min(7, 7+2) = 7.

Всі вершини мають остаточні позначки.

При розв’язанні слід відразу на графі позначити остаточні позначки вершин.

Таким чином найкращий шлях з початкової вершини до кінцевої вершини дорівнює 7.

Також ми маємо найкоротший шлях з початкової вершини до будь-якої вершини графа.

На графі слід також позначити цей найкоротший шлях.

Приклад 2 Розглянемо приклад мережевого графа.

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

,

де d_j – позначка j-ої вершини, c_ij – вага дуги (i, j).

Вершини, що остаточно позначені, об’єднаємо в множину I^*.

Вершини, сусідні з позначеними, об’єднаємо в множину ω (I^*).

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

I. d ₁ = 0 (за формулою). Тобто вершина остаточно позначена і має позначку .

На цьому етапі

I^* = {1},

ω (I^*) = {2, 3, 4} – множина вершин, сусідніх з позначеними.

Знайдемо тимчасові позначки вершин множини ω (I^*) за формулою .

d ₂ = 0+2 = 2,

d ₃ = 0+1 = 1,

d ₄ = 0+4 = 4.

З усіх тимчасових позначок вибираємо найменшу: . Таким чином, вершина одержує остаточну позначку .

II. I^* = {1, 3}, ω (I^*) = {2, 4, 5, 6}.

d ₂ = 0+2 = 2,

d ₄ = min(0+4, 1+2) = 3,

d ₅ = 1+5 = 6,

d ₆ = 1+6 = 7.

– вершина одержує остаточну позначку .

III. I^* = {1, 2, 3}, ω (I^*) = {4, 5, 6, 7}.

d ₄ = min(2+3, 0+4, 1+2) = 3,

d ₅ = min(2+4, 1+5) = 6,

d ₆ = 1+6 = 7,

d ₇ = 2+6 = 8.

– остаточно позначається вершина позначкою .

IV. I^* = {1, 2, 3, 4}, ω (I^*) = {5, 6, 7}.

d ₅ = min(1+5, 3+1, 2+4) = 4,

d ₆ = 1+6 = 7,

d ₇ = 2+6 = 8.

– остаточно позначається вершина позначкою .

V. I^* = {1, 2, 3, 4, 5}, ω (I^*) = {6, 7, 8}.

d ₆ = min(1+6, 4+1) = 5,

d ₇ = min(2+6, 4+3) = 7,

d ₈ = 4+5 = 9.

– остаточно позначається вершина позначкою .

VI. I^* = {1, 2, 3, 4, 5, 6}, ω (I^*) = {7, 8}.

d ₇ = min(2+6, 4+3) = 7,

d ₈ = min(5+2, 4+5) = 7.

– остаточно позначається вершина позначкою .

Ми одержали дві однакові позначки. В цьому випадку остаточно позначаємо вершину з меншим номером.

VII. I^* = {1, 2, 3, 4, 5, 6, 7}, ω (I^*) = {8}.

d ₈ = min(7+4, 5+2, 4+5) = 7.

Остаточно позначимо вершину позначкою .

Таким чином, довжина найкоротшого шляху в графі дорівнює 7. Зобразимо граф з позначками і покажемо найкоротший шлях з вершини до вершини .

Найкоротший шлях в графі:

.

Приклад 3 Знайти найдовший шлях у графі.

Вершини, що остаточно позначені, об’єднаємо в множину I^*.

Вершини, сусідні з позначеними, об’єднаємо в множину ω (I^*).

Тут в сусідні включаються ті вершини, для яких всі дуги йдуть з остаточно позначених вершин.

d ₁ = 0 – остаточно позначена вершина позначкою .

I. I^* = {1}, ω (I^*) = {2, 3}.

d ₂ = 0+2 = 2,

d ₃ = 0+1 = 1.

– остаточно позначається вершина позначкою .

II. I^* = {1, 2}, ω (I^*) = {3}.

d ₃ = 0+1 = 1.

Остаточно позначається вершина позначкою .

III. I^* = {1, 2, 3}, ω (I^*) = {4}.

d ₄ = max(0+4, 2+3, 1+2) = 5.

Остаточно позначається вершина позначкою .

IV. I^* = {1, 2, 3, 4}, ω (I^*) = {5}.

d ₅ = max(2+4, 5+1, 1+5) = 6.

Остаточно позначається вершина позначкою .

V. I^* = {1, 2, 3, 4, 5}, ω (I^*) = {6, 7}.

d ₆ = max(1+6, 6+1) = 7,

d ₇ = max(2+6, 6+3) = 9.

Остаточно позначається вершина позначкою .

VI. I^* = {1, 2, 3, 4, 5, 7}, ω (I^*) = {6}.

d ₆ = max(1+6, 6+1) = 7,

Остаточно позначається вершина позначкою .

VII. I^* = {1, 2, 3, 4, 5, 6, 7}, ω (I^*) = {8}.

d ₆ = max(9+4, 6+5, 7+2) = 13.

Вершина остаточно позначається позначкою .

Це і є довжина найдовшого шляху в графі. Зобразимо цей шлях і позначимо вершини.

Найдовший шлях у графі

Довжина цього шляху дорівнює 13.