Перегляд вихідного коду сторінки Алгоритм Дейкстри

{{Картка_алгоритм
|клас=[[Алгоритм пошуку]]
|зображення=[[Файл:Dijkstra Animation.gif|Час виконання алгоритму]]
|дані=[[Граф (математика)|Граф]]
|час=<math>O(|E| + |V| \log|V|)</math>
|пропуски=
|оптимальний=
}}
{{Алгоритми пошуку графами}}

'''Алгоритм Дейкстри'''&nbsp;— [[алгоритм]] на [[Граф (математика)|графах]], відкритий [[Дейкстра Едсгер|Дейкстрою]]. Знаходить [[найкоротший шлях]] від однієї вершини графу до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без ребер від'ємної довжини.

== Формулювання задачі ==
''Варіант 1.'' Дана мережа автомобільних доріг, що з'єднують міста Львівської області. Знайти найкоротшу відстань від Львова до кожного міста області, якщо рухатись можна тільки по дорогах.

''Варіант 2.'' Дана карта велосипедних доріжок Латвії та Білорусі. Знайти мінімальну відстань, яку треба проїхати, щоб дістатися від Риги до Бобруйська.

''Варіант 3.'' Є план міста з нанесеними на нього місцями розміщення пожежних частин. Знайти найближчу до кожного дому пожежну станцію.

== Абстракція ==
Дано неорієнтований зв'язний [[Граф (математика)|граф]] '''G'''('''V''', '''U'''). Знайти відстань від вершини '''a''' до всіх інших вершин '''V'''.

== Інтуїтивне пояснення ==
Зберігатимемо поточну мінімальну відстань до всіх вершин '''V''' (від даної вершини '''a''') і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівними нескінченості, а до вершини '''а'''&nbsp;— нулю.
[[Файл:Dijkstra graph0.PNG]]
Розглянемо виконання алгоритму на прикладі. Хай потрібно знайти відстані від 1-ї вершини до всіх інших. Кружечками позначені вершини, лініями&nbsp;— шляхи між ними («дуги»). Над дугами позначена їх «ціна»&nbsp;— довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини.

=== Крок 1 ===
Ініціалізація. Відстань до всіх вершин [[Граф (математика)|графу]] '''V''' = <math>\infty</math>. Відстань до '''а''' = 0. Жодної вершини графу ще не опрацьовано.<br/>[[Файл:Dijkstra graph1.PNG]]

=== Крок 2 ===
Знаходимо таку вершину (із ще не опрацьованих), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда. <br/>
[[Файл:Dijkstra graph2.PNG]]

=== Крок 3 ===
Перший по порядку сусід 1-ї вершини&nbsp;— 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7. <br/>
[[Файл:Dijkstra graph3.PNG]]

=== Кроки 4, 5 ===
Аналогічну операцію проробляємо з двома іншими сусідами 1-ї вершини&nbsp;— 3-ю та 6-ю. <br/>
[[Файл:Dijkstra graph4.PNG]]
[[Файл:Dijkstra graph5.PNG]]

=== Крок 6 ===
Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною і обговоренню не підлягає (те, що це дійсно так, вперше довів [[Дейкстра Едсгер|Дейкстра]]). Тому викреслимо її з [[Граф (математика)|графу]], щоб відмітити цей факт.
[[Файл:Dijkstra graph6.PNG]]

=== Крок 7 ===
Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7. [[Файл:Dijkstra graph7.PNG]]
І знову намагаємося зменшити відстань до всіх сусідів 2-ї вершини, намагаючись пройти в них через 2-у. Сусідами 2-ї вершини є 1, 3, 4.

=== Крок 8 ===
Перший (по порядку) сусід вершини №&nbsp;2&nbsp;— 1-ша вершина. Але вона вже оброблена (або викреслена&nbsp;— див. крок 6). Тому з 1-ю вершиною нічого не робимо.

=== Крок 8 (з іншими вхідними даними) ===
Інший сусід вершини 2&nbsp;— вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ї + відстань між 2-ю і 4-ю вершинами = 7 + 15 = 22. Оскільки 22 < ∞, встановлюємо відстань до вершини №&nbsp;4 рівним 22.
[[Файл:Dijkstra graph8.PNG]]

=== Крок 9 ===
Ще один сусід вершини 2&nbsp;— вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини №&nbsp;3 і дорівнює 9, тому поточну відстань до 3-ї вершини не міняємо.
[[Файл:Dijkstra graph9.PNG]]

=== Крок 10 ===
Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і викреслюємо її з [[Граф (математика)|графу]].
[[Файл:Dijkstra graph10.PNG]]

=== Кроки 11&nbsp;— 15 ===
По вже «відпрацьованій» схемі повторюємо кроки 2&nbsp;— 6. Тепер «найближчою» виявляється вершина №&nbsp;3. Після її «обробки» отримаємо такі результати: <br/>
[[Файл:Dijkstra graph11.PNG]]

=== Наступні кроки ===
Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5). <br/>
[[Файл:Dijkstra graph12.PNG]]
[[Файл:Dijkstra graph13.PNG]]
[[Файл:Dijkstra graph14.PNG]]

=== Завершення виконання алгоритму ===
Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ї вершини до 2-ї становить 7, до 3-ї&nbsp;— 9, до 4-ї&nbsp;— 20, до 5-ї&nbsp;— 20, до 6-ї&nbsp;— 11 умовних одиниць.

== Найпростіша реалізація ==
Найпростіша реалізація алгоритму Дейкстри потребує '''<math>O(V^2)</math>''' дій. У ній використовується масив відстаней та масив позначок.
На початку алгоритму відстані заповнюються великим додатнім числом (більшим максимального можливого шляху в [[Граф (математика)|графі]]), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

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

== У математичних термінах ==
Нехай u&nbsp;— вершина, від якої шукаються відстані, V&nbsp;— множина вершин [[Граф (математика)|графу]], d<sub>i</sub>&nbsp;— відстань від вершини u до вершини i, , w<sub>(i, j)</sub>&nbsp;— вага «ребра» (i, j).

Алгоритм:

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

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

3. ''Потенційні відстані'' D<sub>i</sub> до вершин з V\U встановлюються нескінченними.

4. Для всіх ребер (i, j), де i∈U та j∈V\U, якщо D<sub>j</sub>>d<sub>i</sub>+w<sub>(i, j)</sub>, то D<sub>j</sub> присвоюється d<sub>i</sub>+w<sub>(i, j)</sub>.

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

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

== Див. також ==
* [[Задача комівояжера]]
* [[Алгоритм пошуку A*]]

== Посилання ==
{{Commons category}}
* [https://www.youtube.com/watch?v=GazC3A4OQTE Пояслення алгоритму Дейкстри] {{Webarchive|url=https://web.archive.org/web/20210709200546/https://www.youtube.com/watch?v=GazC3A4OQTE |date=9 липня 2021 }} на каналі "Computerphile" на YouTube {{ref-en}}
* [http://algolist.manual.ru/maths/graphs/shortpath/dijkstra.php algolist.manual.ru] {{Webarchive|url=https://web.archive.org/web/20061205224440/http://algolist.manual.ru/maths/graphs/shortpath/dijkstra.php |date=5 грудня 2006 }}
* [https://web.archive.org/web/20120628080755/http://www.cs.auckland.ac.nz/~jmor159/PLDS210/dijkstra.html Опис, код, анімація] на сайті університету Окланда {{ref-en}}
* C. Анисимов. [http://faqs.org.ru/progr/graph/pathmake.htm Как построить кратчайший маршрут между двумя точками.] {{Webarchive|url=https://web.archive.org/web/20101126195914/http://faqs.org.ru/progr/graph/pathmake.htm |date=26 листопада 2010 }}
* [http://e-maxx.ru/algo/dijkstra Реализация простейшего варианта алгоритма Дейкстры на e-maxx.ru] {{Webarchive|url=https://web.archive.org/web/20100820032741/http://e-maxx.ru/algo/dijkstra |date=20 серпня 2010 }}
* [http://e-maxx.ru/algo/dijkstra_sparse Реализация варианта алгоритма Дейкстры для разреженных графов на e-maxx.ru] {{Webarchive|url=https://web.archive.org/web/20100820065449/http://e-maxx.ru/algo/dijkstra_sparse |date=20 серпня 2010 }}
* [http://iu9.wikidot.com/dijkstra Реализация на основе очереди с приоритетами на C++] {{Webarchive|url=https://web.archive.org/web/20100826191229/http://iu9.wikidot.com/dijkstra |date=26 серпня 2010 }}
* [http://sites.google.com/site/indy256/algo/dijkstra_heap Реализация на основе очереди с приоритетами на Java] {{Webarchive|url=https://web.archive.org/web/20110211061112/http://sites.google.com/site/indy256/algo/dijkstra_heap |date=11 лютого 2011 }}
* [https://www.mathros.net.ua/znahodzhennja-najkorotshogo-shljahu-v-orijentovanomu-grafi-za-algorytmom-dejkstry.html| Алгоритм Дейкстри з прикладами - mathros.net.ua]

{{Algorithms-stub}}

[[Категорія:Алгоритми на графах|Дейкстри]]
[[Категорія:Винаходи Нідерландів]]
[[Категорія:Едсгер Дейкстра]]
[[Категорія:Статті з прикладами коду мовою C++]]