ву вібіраємо вершину, найближче до a та не Вибраного Ранее; повторюємо процес.
Описаний процес Зручне Виконувати помощью прісвоювання вершин міток. Є Мітки двох тіпів: Тимчасові та постійні. Вершини з постійнімі міткамі групують у множини M, якові назівають множини Позначення вершин. Решта вершин має Тимчасові Мітки, и множини таких вершин позначімо як T, T=V M. Позначатімемо мітку (тимчасову чи постійну) вершини v як l (v). Значення постійної Мітки l (v) дорівнює довжіні найкоротшого шляху від вершини a до вершини v, тімчасової - довжіні найкоротшого шляху, Який проходити лишь через вершини з постійнімі міткамі.
Фіксованою початково вершиною Вважаємо вершину a; Довжину найкоротшого шляху шукаємо до вершини z (або до всіх вершин графа). Розглянемо приклад.
Варіант 1. Дана мережа автомобільних доріг, что з єднують міста України. Знайте найкоротші шляхи від Київа до шкірного міста України (если рухатіся можна только по дорогах).
Варіант 2. Надал Кількість маршрутів ПАСАЖИРСЬКЕ транспорту, для шкірного маршрутом відома его ВАРТІСТЬ. Знайте маршрут мінімальної вартості (можливо, з пересадками), например, от Таїровського житлового масиву до Іллічівська.
У загально випадка алгоритм Дейкстри Заснований на прісвоєнні вершин Тимчасових позначок, причому Позначку вершини дает верхню межу Довжина шляху від деякої вершини s до наданої вершини. ЦІ Позначки поступово зменшуються помощью деякої ітераційної процедури, и на шкірному кроці ітерації только один з Тимчасових позначок становится постійною. Останнє указує на том, что Позначку Вже НЕ є верхні межею, а дает точно Довжину найкоротшого шляху від t до наданої вершини.
Розглянемо докладніше цею алгоритм. Надано граф G=(X, A, C) Із зваження дугами, приклад которого показано на ріс.5.30 Позначімо L (хi) Позначку вершини хi. Ваги відстаней наведено в табліці.
Малюнок 5.30 - Граф Із зваження дугами
Таблиця - Ваги відстаней
x1x2x3x4x1c1c3x2c2x3c5x4c4
Розглянемо алгоритм знаходження найкоротшого шляху від вершини s до вершини t графа и більш загальний випадок: від вершини s до всіх вершин графа.
Прівоєння початкових позначок.
КРОК 1. Прісвоїті L (s)=0 и вважаті Цю Позначку постійною. Для всіх вершин хi s покласть L (хi) =? и вважаті ЦІ Позначки Тимчасовими. За поточних Дану вершину з постійною Позначку візьмемо вершину p, тобто покласть p=s.
Оновлення позначок
КРОК 2. Для вершин, что входять в прямому відображення вершини р, тобто для всіх хi, належности Г (p), Позначки якіх Тимчасові, Сменить Позначки відповідно до следующего вирази:
(xi) ¬ min [L (xi), L (p) + C (p, xi)] (5.1)
Перетворення Позначки в постійну.
КРОК 3. Серед всех вершин з Тимчасовими Позначку найти таку, для якої L ()=min [L (xi)].
КРОК 4. рахувати Позначку вершини постійною и покласть p =.
КРОК 5 (а). (При знаходженні шляху від s до t) - если поточна вершина p є шуканою, тобто p=t, то L (p) є довжина найкоротшого шляху від s до t. Если pt, перейти до КРОК 2.
КРОК 5 (б). (При знаходженні Шляхів від s до всіх вершин)
- если всі вершини відмічені постійнімі Позначку, то ЦІ Позначки дають Довжина найкоротшіх Шляхів;
- если деякі Позначку є Тимчасовими, то слід перейти до КРОК 2.
Як только Довжина найкоротшіх Шляхів від вершини s будут знайдені, шляхи можна здобудуть помощью рекурсівної процедури (*). Оскількі вершина безпосередно передує вершіні хi в найкоротшому шляху від s до хi, то для будь-якої вершини хi відповідну вершину можна найти як одну з вершин, что залиша, для якої
() + c (, xi)=L (xi) (5.2)
Если найкоротшій шлях від s до будь-якої вершини хi є Єдиним, то дуги (, xi) цього найкоротшого шляху утворюють орієнтоване дерево з коренем s.
Если існує декілька найкоротшіх Шляхів від s до якої-небудь Іншої вершини, то при деякій фіксованій вершіні співвідношення (*) віконуватіметься для більш чем однієї вершини хi. У цьом випадка вибір может буті або довільнім (если потрібен Якийсь одна найкоротшій шлях между s и хi), або таким, что розглядаються всі дуги (, x2), что входять в Який-небудь з найкоротшіх Шляхів, и при цьом сукупність всех таких дуг утворює НЕ орієнтоване дерево, а загальний граф, звань базою относительно s.
Приклад. Розглянемо граф змішаного типу, збережений на рис. 5.31 (а), де Кожне неорієнтоване ребро розглядається як пара протилежних...
