Як вирішити проблему найкоротшого шляху з одного джерела за допомогою алгоритму Дейкстри?
2024Алгоритм найкоротшого шляху Дейкстри обчислює найкоротший шлях між вузлами. Алгоритм підтримує зважені графіки з додатними вагами зв’язку. Алгоритм одного джерела Дейкстри обчислює найкоротші шляхи між вихідним вузлом і всіма вузлами, доступними з цього вузла.
Алгоритм Дейкстри
- Позначте кінцеву вершину нульовою відстанню. Позначте цю вершину поточною.
- Знайти всі вершини, що ведуть до поточної вершини. Обчисліть їх відстані до кінця. …
- Позначте поточну вершину як відвідану. …
- Позначте вершину з найменшою відстанню як поточну та повторіть з кроку 2.
Алгоритм Дейкстри вирішує проблему найкоротшого шляху з одним джерелом, якщо всі ваги ребер більші або дорівнюють нулю. Без погіршення складності часу виконання, цей алгоритм фактично може обчислити найкоротші шляхи від даної початкової точки s до всіх інших вузлів.
Ми визначаємо вагу найкоротшого шляху від u до v за допомогою δ(u,v) = min (w (p): u→v), якщо є шлях від u до v, і δ(u,v)= ∞, інакше. Найкоротший шлях від вершини s до вершини t тоді визначається як будь-який шлях p з вагою w (p) = δ(s,t).
Алгоритм Дейкстри використовується для знаходження найкоротшого шляху між двома згаданими вершинами графа шляхом застосування алгоритму Жадібного як основи принципу. Наприклад: Використовується для пошуку найкоротшого пункту призначення для відвідування від вашого поточного місцезнаходження на карті Google.
Алгоритм Дейкстри знаходить найкоротший шлях між даним вузлом (який називається «вихідним вузлом») та всіма іншими вузлами в графі. Цей алгоритм використовує ваги ребер, щоб знайти шлях, який мінімізує загальну відстань (вагу) між вихідним вузлом і всіма іншими вузлами.