ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Знаходження найкоротшого шляху в орієнтованому графі

Задано орієнтований граф. Кожній дузі, що з’єднує вершину ui з вершиною uj (uiuj), відповідає невід’ємне число cij > 0. Це число називаємо вагою дуги.

Питання, що тут виникають:

1 Яка довжина найкоротшого шляху між будь-якими двома вершинами графа?

2 Які довжини найкоротших шляхів між виділеною вершиною та іншими вершинами?

3 Які довжини шляхів між усіма парами вершин, що це за шляхи?

Один із методів розв’язання таких задач – це алгоритм Дейкстри (розв’язок одержано у 1960р., автор – Дейкстра).

При роботі цього алгоритма будемо користуватись такими правилами:

1) позначаємо вершини значеннями їх відстаней від виділеної вершини;

2) до остаточної позначки вершині присвоюється тимчасова позначка; ця тимчасова позначка дає відстань від виділеної вершини, коли множина шляхів складається не з усіх можливих;

3) алгоритм припиняє роботу тоді, коли позначка кінцевої вершини не змінюється;

4) у кожний момент роботи алгоритма деякі вершини мають остаточні позначки, а решта не мають.

Крок ІПочатковій вершині присвоюється остаточна позначка «0», а іншим вершинам – тимчасова позначка «∞».

Крок ІІКожній вершині х, яка не має остаточної позначки, присвоюється нова тимчасова позначка за правилом :

min(dx, dy+cyx),

де dx – стара тимчасова позначка вершини х;

у – вершина, яка одержала остаточну позначку на попередньому кроці;

cyx – вага дуги (у,х).

Крок ІІІЗнаходимо найменшу з усіх тимчасових позначок і оголошуємо її остаточною позначкою відповідної вершини. Ця вершина грає роль вершини у для наступного кроку.

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

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

1 d1=0, di=∞, де i = 2,3,4,5,6.

2 = => dy = 0,

d2 = min(∞,0+4) = 4,

d3 = min(∞,0+2) = ,

d4 = min(∞,0+7) = 7,

d5 = min(∞,0+∞) = ∞,

d6 = min(∞,0+∞) = ∞.

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

3 = => dy = 2,

d2 = min(4,2+∞) = ,

d4 = min(7,2+∞) = 7,

d5 = min(∞,2+3) = 5,

d6 = min(∞,2+∞) = ∞.

4 = => dy = 4,

d4 = min(7,4+3) = 7,

d5 = min(5,4+2) = ,

d6 = min(∞,4+∞) = ∞.

5 = => dy = 5,

d4 = ,

d6 = min(∞,5+2) = 7.

6 = => dy = 7,

d6 = min(7,7+2) = 7.

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

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

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

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

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

Існує ще один спосіб для знаходження екстремального шляху в графі – спосіб позначок.

Розглядаємо орієнтований граф, який називається мережевим. В такому графі існує одна вершина, з якої дуги лише виходять (витік, джерело), і одна вершина, в яку дуги лише входять (стік). Крім того, вершини такого графа можуть бути пронумеровані таким чином, що наступні по напрямку руху вершини (послідовники) мають більші номери, ніж попередні (попередники). Тоді всі вершини графа можна розбити на шари таким чином, що вершини кожного шару з номером m (m > 1) будуть послідовниками вершин із шарів з меншими ніж m номерами і попередниками вершин із шарів з більшими ніж m номерами.

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

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

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

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

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

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

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

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

I* = {1},

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

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

d2 = 0+2 = 2,

d3 = 0+1 = 1,

d4 = 0+4 = 4.

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

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

d2 = 0+2 = 2,

d4 = min(0+4,1+2) = 3,

d5 = 1+5 = 6,

d6 = 1+6 = 7.

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

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

d4 = min(2+3,0+4,1+2) = 3,

d5 = min(2+4,1+5) = 6,

d6 = 1+6 = 7,

d7 = 2+6 = 8.

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

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

d5 = min(1+5,3+1,2+4) = 4,

d6 = 1+6 = 7,

d7 = 2+6 = 8.

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

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

d6 = min(1+6,4+1) = 5,

d7 = min(2+6,4+3) = 7,

d8 = 4+5 = 9.

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

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

d7 = min(2+6,4+3) = 7,

d8 = min(5+2,4+5) = 7.

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

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

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

d8 = min(7+4,5+2,4+5) = 7.

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

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

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

.

Спосіб позначок можна застосувати і для знаходження найдовшого шляху в мережевому графі. При цьому в сусідні вершини (множина ω(I*)) будемо включати лише ті, для яких усі дуги, що ведуть в цю вершину, починаються в I* – множині остаточно позначених вершин.

Формула, за якою треба діяти в цьому випадку, має вигляд

На кожному кроці роботи алгоритма в якості остаточно позначеної вершини беремо вершину з максимальною позначкою.

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

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

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

d2 = 0+2 = 2,

d3 = 0+1 = 1.

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

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

d3 = 0+1 = 1.

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

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

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

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

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

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

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

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

d6 = max(1+6,6+1) = 7,

d7 = max(2+6,6+3) = 9.

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

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

d6 = max(1+6,6+1) = 7,

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

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

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

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

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

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

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

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти