В теорії графів, задача про найкоротший шлях полягає в знаходженні такого шляху між двома вершинами (або вузлами) графу, що сума ваг ребер з яких він складається мінімальна. Прикладом може бути знаходження найкоротшого шляху між двома пунктами на дорожній мапі; в цьому випадку, вершинами є пункти, а ребрами — відтинки дороги із вагами, рівними часу, необхідному для подолання цього відрізку.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODFMelZpTHpadUxXZHlZV1l1YzNabkx6SXlNSEI0TFRadUxXZHlZV1l1YzNabkxuQnVadz09LnBuZw==.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHpMek5pTDFOb2IzSjBaWE4wWDNCaGRHaGZkMmwwYUY5a2FYSmxZM1JmZDJWcFoyaDBjeTV6ZG1jdk1qVXdjSGd0VTJodmNuUmxjM1JmY0dGMGFGOTNhWFJvWDJScGNtVmpkRjkzWldsbmFIUnpMbk4yWnk1d2JtYz0ucG5n.png)
Формально, маємо зважений граф (це набір вершин V і ребер E з дійсно-значимою функцією ваги f : E → R), і заданим елементом v з V, знайти шлях P з v до v' з V такий, що
найменша серед усіх шляхів, що зв'язують v з v' .
Така задача іноді згадується як Задача про найкоротший шлях між парою вершин, щоб відрізнити від наступних узагальнень:
- Задача про найкоротші шляхи з одного входу, тут ми маємо знайти найкоротші шляхи між вхідною вершиною v та всіма іншими вершинами графу.
- Задача про найкоротші шляхи з одним виходом, тут ми маємо знайти найкоротші шляхи з усіх вершин графу до однієї вихідної v. Може бути зведена до задачі з одним входом шляхом зміни на зворотні ребер графу.
- Задача про найкоротші шляхи для всіх пар, тут ми маємо знайти найкоротші шляхи між кожною парою вершин v, v' в графі.
Ці узагальнення мають значно дієвіші алгоритми ніж спрощений підхід із запуском алгоритму пошуку найкоротшого шляху між всіма значимими парами вершин.
Алгоритми
Найважливіші алгоритми для розв'язання цієї задачі:
- Алгоритм Дейкстри розв'язує задачі з однією парою, одним входом і одним виходом.
- (Алгоритм Беллмана — Форда) розв'язує задачі з одним входом, якщо ваги ребер можуть бути від'ємні.
- Алгоритм пошуку A* розв'язує задачу для однієї пари із використанням евристики в спробі пришвидшити пошук.
- (Алгоритм Флойда — Воршелла) розв'язує задачу для всіх пар.
- (Алгоритм Джонсона) розв'язує задачу для всіх пар, і може бути швидшим за алгоритм Флойда-Воршелла на (розріджених графах).
- Теорія збурень знаходить (в найгіршому випадку) локально найкоротший шлях.
Див. також
- (Задача про найширший шлях)
- Потокова мережа
Посилання
Ця стаття не містить . (липень 2013) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет