кладі графа, показаного на малюнку 4. Нехай потрібно знайти найкоротші відстані від 1-й вершини до всіх інших.
Кружками позначені вершини, лініями - шляху між ними (ребра графа). У гуртках позначені номери вершин, над ребрами позначена їх «ціна» - довжина шляху. Поряд з кожною вершиною червоним позначена мітка - довжина найкоротшого шляху в цю вершину з вершини 1.
Перший крок. Розглянемо крок алгоритму Дейкстри для нашого прикладу. Мінімальну мітку має вершина 1. Її сусідами є вершини 2, 3 і 6.
Рис. 4
Рис. 5
Рис. 6
Перший по черзі сусід вершини 1 - вершина 2, тому що довжина шляху до неї мінімальна. Довжина шляху в неї через вершину 1 дорівнює сумі значення мітки вершини 1 і довжини ребра, що йде з 1-й в 2-ю, тобто 0 + 7=7. Це менше поточної мітки вершини 2, нескінченності, тому нова мітка 2-й вершини дорівнює 7.
Рис. 7
Аналогічну операцію проробляємо з двома іншими сусідами 1-й вершини - третій і 6-й.
Рис. 8
Всі сусіди вершини 1 перевірені. Поточне мінімальна відстань до вершини 1 вважається остаточним і перегляду не підлягає (те, що це дійсно так, уперше довів Е. Дейкстра). Викреслимо її з графа, щоб відзначити, що ця вершина переглянуло.
Рис. 9
Другий крок. Крок алгоритму повторюється. Знову знаходимо «найближчу» з невідвіданих вершин. Це вершина 2 з міткою 7.
Рис. 10
Знову намагаємося зменшити мітки сусідів обраної вершини, намагаючись пройти в них через 2-ю вершину. Сусідами вершини 2 є вершини 1, 3 і 4.
Перший (по порядку) сусід вершини 2 - вершина 1. Але вона вже переглянуло, тому з 1-й вершиною нічого не робимо.
Наступний сусід вершини 2 - вершина 3, оскільки має мінімальну мітку з вершин, відзначених що не відвідані. Якщо йти в неї через 2, то довжина такого шляху буде дорівнює 17 (7 + 10=17). Але поточна мітка третій вершини дорівнює 9, а це менше 17, тому мітка не змінюється.
Рис. 11
Ще один сусід вершини 2 - вершина 4. Якщо йти в неї через 2-ю, то довжина такого шляху буде дорівнює сумі найкоротшої відстані до 2-й вершини і відстані між вершинами 2 і 4, тобто 22 (7 + 15=22). Оскільки, встановлюємо мітку вершини 4 рівний 22.
Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і помічаємо її як відвіданих.
Рис. 12
Рис. 13
Третій крок. Повторюємо крок алгоритму, вибравши вершину 3. Після її «обробки» отримаємо такі результати:
Рис. 14
Подальші кроки. Повторюємо крок алгоритму для залишилися вершин. Це будуть вершини 6, 4 і 5, відповідно до порядку.
Рис. 15
Завершення виконання алгоритму. Алгоритм закінчує роботу, коли не можна більше обробити жодної вершини. У даному прикладі всі вершини закреслено, проте помилково вважати, що так буде в кожному прикладі - деякі вершини можуть залишитися незачеркнутимі, якщо до них не можна добратися. Результат роботи алгоритму видно на останньому малюнку: найкоротший шлях від вершини 1 до 2-й становить 7, до третього - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.
. 2 Аналіз алгоритму Флойда
Алгоритм Флойда - динамічний алгоритм для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблено в 1962 році Робертом Флойдом, хоча в 1959 році Бернард Рой (Bernard Roy) опублікував практично такий же алгоритм, але це залишилося непоміченим.
Цей алгоритм більш загальний порівняно з алгоритмом Дейкстри, оскільки він знаходить найкоротші шляхи між будь-якими двома вузлами мережі. У цьому алгоритмі мережа представлена ??у вигляді квадратної матриці з n рядками і n стовпцями. Елемент (i, j) дорівнює відстані d ij від вузла i до вузла j, яке має кінцеве значення, якщо існує дуга (i, j), і дорівнює нескінченності в іншому випадку.
Покажемо спочатку основну ідею методу Флойда. Нехай є три вузли i, j і k і задані відстані між ними (рис. 1). Якщо виконується нерівність d ij + d jk lt; d ik, то доцільно замінити шлях i - gt; k шляхом i - gt; j - gt; k. Така заміна (далі її будемо умовно називати трикутним оператором) виконується систематично в процесі виконання алгоритму Флойда.
Рис.16. Трикутний оператор
