Матеріал з Вікіпедії — вільної енциклопедії.

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від одної вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без дуг від'ємної довжини.

Зміст 1 Формулювання задачі 2 Абстракція 3 Інтуїтивне пояснення 3.1 Крок 1 3.2 Крок 2 3.3 Крок 3 3.4 Кроки 4, 5 3.5 Крок 6 3.6 Крок 7 3.7 Крок 8 3.8 Крок 8 (з іншими вхідними данними) 3.9 Крок 9 3.10 Крок 10 3.11 Кроки 11 — 15 3.12 Наступні кроки 3.13 Завершення виконання алгоритму 4 Найпростіша реалізація 5 В математичних термінах 5.1 Посилання 5.2 Джерела інформації

[ред.] Формулювання задачі

Варіант 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(V²) дій. У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі),а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

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

[ред.] В математичних термінах

Нехай u — вершина, від якої шукаються відстані, V — множина вершин графа, d_i — відстань від вершини u до вершини i, , w_{(i, j)} — вага «ребра» (i, j).

Алгоритм:

1. Множина вершин U, до яких відстань відома, встановлюється рівною {u}.

2. Якщо U=V, алгоритм завершино.

3. Потенційні відстані D_iдо вершин з U\V встановлюються нескінченими.

4. Для всіх ребер (i, j), де i∈U та j∈V\U, якщо D_j>d_i+w_{(i, j)}, то D_j присвоюється d_i+w_{(i, j)}.

5. Шукається i∈V\U, при якому D_i мінімальне.

6. Якщо D_i дорівнює нескінченості, алгоритм завершено. В іншому випадку d_i присвоюється значення D_i, U присвоється U∪{i} і виконується перехід до кроку 2.

[ред.] Посилання

• algolist.manual.ru

[ред.] Джерела інформації

Алгоритм Дейстры— стаття в російськомовній вікіпедії.