Навігація
Главная
Авторизация/Регистрация
 
Головна arrow Природознавство arrow ПРИКЛАДНА МАТЕМАТИКА: ТЕХНОЛОГІЇ ЗАСТОСУВАННЯ
Переглянути оригінал

ПОШУК ШЛЯХІВ НА ГРАФІ

Постановка задачі. Нехай заданий орієнтований граф G (X, А ). Зафіксуємо дві його вершини: початкову s і кінцеву t. Потрібно знайти найкращий в деякому сенсі шлях з s в t.

Найбільш важливим окремим випадком такого завдання є завдання про пошук найкоротшого шляху. Припустимо, що кожній дузі (х, у) графа G поставлено у відповідність число з (х, у), зване довжиною дуги. Довжину шляху визначимо як суму довжин виділених дуг, що складають цей шлях. Ясно, що між двома вершинами графа може бути один шлях, більш одного дорозі або не бути жодного шляху. Поставимо задачу знаходження на даному графі G (мережі) найкоротшого (в сенсі довжини) шляху з s в t.

Легко бачити, що з математичної точки зору поставлена задача проста: побудувати з s в t всі можливі шляхи і вибрати з них той, у якого довжина шляху найменша. На практиці ж такий спосіб зазвичай не застосуємо, оскільки є реалізацією методу повного перебору варіантів і призводить до дуже тривалій процедурі рішення.

Одним з варіантів раціонального побудови найкоротшого шляху на бесконтурном графі з невід'ємними вагами дуг є алгоритм, який запропонував Е. Дейкстра в 1959 р Ідея його методу рішення полягає в поступовому нарощуванні покриває прадерева, виходячи з кореня s. Розглянемо її трохи докладніше. Нехай пофарбована вершина 5 і т найближчих до неї вершин. Найближчими до s назвемо ті вершини, для яких побудований (забарвлений) найкоротший шлях. Наступна + 1) -я найближча до 5 вершина може бути знайдена так. Виберемо всі незабарвлені суміжні по відношенню до пофарбованих вершини {у ; }. Для кожної вершини у, побудуємо умовно найкоротший шлях (найкоротший з 5 в дану вершину у,). Потім з усіх умовно найкоротших шляхів виберемо найкоротший. Відповідну цього обраному шляху незабарвлену вершину і інцидентності їй дугу офарблюємо. Тепер є (m + 1) найближчих до s вершин. Процедура повторюється до тих пір, поки не буде пофарбована вершина t.

Алгоритм пошуку найкоротшого шляху. Нехай задано початковий стан мережі: всі вершини не пофарбовані і виділені дві вершини витік 5 і стік t. Для кожної вершини х, - водиться величина d (x,) дорівнює довжині найкоротшого шляху з 5 в х "включає лише пофарбовані вершини.

  • 1. Пофарбувати вихідну вершину s, позначити у = s і покласти d (s) = 0, а для всіх нефарбованих вершин х, - d (x,) =
  • 2. Вибрати вершину х *, перерахувавши величини d (x ; ) для всіх нефарбованих вершин х ; , Суміжних з пофарбованими вершинами ур за формулою

  • 3. Забарвлюється вершина х "і найкоротша дута, що зв'язує її з раніше пофарбованої вершиною. Якщо х * = t, то задача вирішена. Пофарбований шлях з s в t - шуканий найкоротший шлях. В іншому випадку перейти до п. 4.
  • 4. Якщо серед нефарбованих вершин немає дуть, провідних в нефарбовані вершини, то задача не має рішення. В іншому випадку перейти до п. 2.

Примітка 16.4. Оскільки алгоритм побудови найкоротшого шляху на графі відповідає процедурі нарощування орієнтованого дерева з коренем у вершині s, будь-яка вершина у-, що входить в це дерево, з'єднана з вершиною 5 найкоротшим шляхом. Таким чином, як би автоматично вирішується завдання побудови найкоротшого шляху в ряд інших вершин.

Примітка 16.5. Якщо відповідно до описаного алгоритму виявляться пофарбованими все вершини, то буде побудовано покриває граф орієнтоване дерево найкоротших шляхів від вершини s до всіх інших вершин вихідного графа.

приклад 16.3

Побудувати найкоротший шлях між вершинами 5 і t на графі, зображеному на рис. 16.17.

Вихідний граф для завдання про найкоротшому шляху

Мал. 16.17. Вихідний граф для завдання про найкоротшому шляху

Рішення. Згідно описаного алгоритму реалізуємо наступний процес.

Крок 1. Забарвлена вершина s, d (s) = 0.

Крок 2. Відповідно до формули (16.1) маємо

Найменша величина d (x) відповідає вершині с. Тому фарбуються дуга (5, с) і вершина з (рис. 16.18). Оскільки пофарбований не вершина t, то проводимо наступний крок.

Фарбування вершин на кроці 2

Мал. 16.18. Фарбування вершин на кроці 2

Крок 3. Відповідно до формули (16.1) маємо

Офарблюємо дугу (s, а) і вершину а (рис. 16.19). Оскільки не пофарбована вершина t, то робимо наступний крок.

Фарбування вершин на кроці 3

Мал. 16.19. Фарбування вершин на кроці 3

Крок 4. Відповідно до формули (16.1) маємо

Забарвлюється вершина d. Вона з'єднана з вершиною s шляхом довжиною 6 через вершину а (рис. 16.20). Оскільки знову не пофарбована вершина t, то робимо наступний крок.

Фарбування вершин на кроці 4

Мал. 16.20. Фарбування вершин на кроці 4

Крок 5. Відповідно до формули (16.1) маємо

Забарвлюється вершина b і дуга (s, b) (рис. 16.21).

Фарбування вершин на кроці 5

Мал. 16.21. Фарбування вершин на кроці 5

Крок 6. Відповідно до формули (16.1) маємо

Забарвлена вершина t, тобто знайдений найкоротший шлях (5, видання, t), довжина якого 8 од. (рис. 16.22).

Побудова остаточного шляху

Мал. 16.22. Побудова остаточного шляху

 
Переглянути оригінал
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук