Алгоритм Дейкстри
Матеріал з Вікіпедії — вільної енциклопедії.
Алгоритм Дейкстри — алгоритм на графах, відкрит Дейкстрою. Знаходить найкоротший шлях від одної вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без дуг від'ємної довжини.
Зміст |
[ред.] Формулювання задачі
Варіант 1. Дана мережа автомобільних доріг, з’єднуючих міста Львівскої області. Знайти найкоротшу відстань від Львова до кожного міста області, якщо рухатись можна тільки по дорогам.
Варіант 2. Дана карта велосипедних доріжек Латвії та Білорусїї. Знайти мінімальну відстань, яку треба проїхати, щоб дістатися від Ріги до Бобруйська.
Варіант 3. Є план міста з нанесенними на нього місцями росположення пожежних частин. Знайти ближчу до кожного дому пожежну станцію.
[ред.] Абстракція
Дан неорієнтований зв’язанний граф граф G(V, U). Знайти відстань від вершини a до всіх інших вершин V.
[ред.] Интуітивне пояснення
Зберігатимемо поточну мінімальну відстань до всіх вершин V (від даної вершини a) і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівним нескінченності, а до вершини а — нулю. Розглянемо виконання алгоритму на прикладі. Хай потрібно знайти відстані від 1-ої вершини до всіх інших. Кружечками позначені вершини, лініями — шляхи між ними («дуги»). Над дугами позначена їх «ціна» — довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини.
[ред.] Крок 1
Ініціалізація. Відстань до всіх вершин графа V =
. Відстань до а = 0. Ні одна вершина графа ще не опрацьована.
[ред.] Крок 2
Знаходимо таку вершину (з ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 меньше поточного мінімального шляху в цю сусідню вершину, то запам'ятовуєм цей новий, більш коротший шлях як поточний найкоротший шлях до сусіда.
[ред.] Крок 3
Перший по порядку сусід 1-ї вершины — 2-а вершина. Шлях до неї через 1-у вершину рівен найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Цу меньше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини рівняється 7.
[ред.] Кроки 4, 5
Аналогічну операцію пророблюєм з двома іншими сусідами 1-ї вершини — 3-ю та 6-ю.
[ред.] Крок 6
Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточним і обговоренню не підлягає (те, що це дійсно так, вперше довів Дейкстра). Тому викреслимо її з графа, щоб відмітити цей факт.
[ред.] Крок 7
Практично відбувається повернення до кроку 2. Знову знаходімо «найбліжчу» необроблену (невікреслену) вершину. Це вершина 2 з поточнім найкоротшою відстанню до неї = 7. І знову намагаємося зменшити відстань до всіх сусідів 2-ої вершини, намагаючись пройти в них через 2-у. Сусідами 2-ої вершини є 1, 3, 4.
[ред.] Крок 8
Перший (по порядку) сусід вершини № 2 — 1-а вершина. Але вона вже оброблена (або викреслена — див. крок 6). Тому з 1-ою вершиною нічого не робимо.
[ред.] Крок 8 (з іншими вхідними данними)
Інший сусід вершини 2 — вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ої + відстань між 2-ою і 4-ою вершинамі = 7 + 15 = 22. Раз 22 < ∞, встановлюємо відстань до вершини № 4 рівним 22.
[ред.] Крок 9
Ще один сусід вершини 2 - вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 > відстані, що вже запам'ятала раніше, до вершини № 3 і рівного 9, тому поточну відстань до 3-ої вершини не міняємо.
[ред.] Крок 10
Всі сусіди вершини 2 проглянуті, заморожуємо відстань до неї і викреслюємо її з графа.
[ред.] Кроки 11 — 15
По вже «відпрацьованій» схемі повторюємо кроки 2 — 6. Тепер «найближчою» виявляється вершина № 3. Після її «обробки» отримаємо такі результати:
[ред.] Наступні кроки
Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).
[ред.] Завершення виконання алгоритму
Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ої вершини до 2-ої складає 7, до 3-ої — 9, до 4-ої — 20, до 5-ої — 20, до 6-ої — 11 умовних одиниць.
[ред.] Найпростіша реалізація
Найпростіша реалізація алгоритма Дейкстри потребує O(V2) дій. У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі),а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.
На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 1 і перевіряємо всі сусідні з нею вершини. Якщо в ній відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то зменшуємо його. Цикл завершується коли позначки всіх вершин стають рівними 1.
[ред.] В математичних термінах
Нехай u — вершина, від якої шукаються відстані, V — множина вершин графа, di — відстань від вершини u до вершини i, , w(i, j) — вага «ребра» (i, j).
Алгоритм:
1. Множина вершин U, до яких відстань відома, встановлюється рівним {u}.
2. Якщо U=V, алгоритм завершино.
3. Потенційні відстані Diдо вершин з U\V встановлюються в нескінченність.
4. Для всіх ребер (i, j), де i∈U та j∈V\U, якщо Dj>di+w(i, j), то Dj присвоюється di+w(i, j).
5. Шукається i∈V\U, при якому Di мінімальне.
6. Якщо Di равно дорівнює безмежність, алгоритм завершено. В іншому випадку di присвоюється значення Di, U присвоється U∪{i} та виконується перехід до кроку 2.
[ред.] Посилання
[ред.] Джерела інформації
Алгоритм Дейстры— стаття в російськомовній вікіпедії.

