Алгоритм Дейкстри (випадок неотрицательной матриці ваг)

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

Опис алгоритму Дейкстра:

Крок 1. Покласти і вважати цю позначку постійної. Покласти для всіх і вважати ці позначки тимчасовими. Покласти.

Крок 2. Для всіх. позначки яких тимчасові, змінити позначки у відповідності з наступним виразом:

Крок 3. Серед усіх вершин з тимчасовими позначками знайти таку, для якої.

Крок 4. Вважати позначку вершини постійної і покласти.

1. Якщо. то є довжиною найкоротшого шляху. Якщо. перейти до кроку 2 (для випадку пошуку шляху від s до t.)

2. Якщо всі вершини відзначені як постійні, то ці позначки дають довжини найкоротших шляхів. Якщо деякі помітки є тимчасовими перейти до кроку 2 (для випадку пошуку шляхів від s до всіх інших вершин).

Як тільки довжини найкоротших шляхів від s будуть знайдені, то самі шляху можна отримати за допомогою рекурсивної процедури з використанням співвідношення (1.2). Так як вершина безпосередньо передує вершині в найкоротшому шляху від s до. то для будь-якої вершини відповідну вершину можна знайти як одну з решти вершин, для якої

Якщо найкоротший шлях від s до будь-якої вершини є єдиним, то дуги цього найкоротшого шляху утворюють орієнтоване дерево з коренем s. Якщо існує декілька "найкоротших" шляхів від s до будь-якої іншої вершини, то при деякій фіксованій вершині співвідношення (2) буде виконуватися для більш ніж однієї вершини. У цьому випадку вибір може бути або довільним (якщо потрібен якийсь один найкоротший шлях між s і), або таким, що розглядаються всі дуги. що входять до будь-якої з найкоротших шляхів, і при цьому сукупність всіх таких дуг утворює не орієнтований дерево, а загальний граф, званий базою щодо s.

Розглянемо граф G, зображений на рис. 1.1, де кожне неорієнтоване ребро розглядається як пара протилежно орієнтованих дуг рівного ваги. Матриця ваг C приведена нижче.

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

Крок 5. Перейти до кроку 2.

Крок 2. - не всі позначки тимчасові, тому зі співвідношення (1.1) отримуємо

Крок 5. Всі вершини мають постійні позначки. Кінець роботи алгоритму. Позначки отримані в результаті роботи алгоритму показані на рис. 1.2 (в).

Знайдемо найкоротший шлях між вершиною і початковою вершиною. послідовно використовуючи співвідношення (1.2). Таким чином, вважаючи. знаходимо вершину. безпосередньо передує в найкоротшому шляху від к. вершина повинна задовольняти співвідношенню

Єдиною такою вершиною є. Далі, застосовуємо вдруге співвідношення (1.2), беручи; отримуємо вершину. безпосередньо передує в найкоротшому шляху від к. Вершина задовольняє співвідношенню

Єдиною такою вершиною є і тому найкоротший шлях від до є.

- база, що дає всі найкоротші шляхи від. являє собою дерево, зображене жирними лініями на рис. 1.2 (в).

Мал. 1.2. (А) Позначки в кінці 1-й ітерації. (Б) Позначки в кінці кроку 2 на 2-й ітерації. (В) Остаточні позначки вершин і - база.