Пошук найкоротшого шляху
9
найменша серед усіх шляхів, що зв'язують v з v'.
Така задача іноді згадується як Задача про найкоротший шлях між парою вершин, щоб відрізнити від наступних узагальнень:
- Задача про найкоротші шляхи з одного входом, тут ми маємо знайти найкоротші шляхи між вхідною вершиною v та всіма іншими вершинами графа.
- Задача про найкоротші шляхи з одним виходом, тут ми маємо знайти найкоротші шляхи з усіх вершин графа до однієї вихідної v. Може бути зведена до задачі з одним входом шляхом зміни на зворотні ребер графа.
- Задача про найкоротші шляхи для всіх пар, тут ми маємо знайти найкоротші шляхи між кожною парою вершин v, v' в графі.
Ці узагальнення мають значно дієвіші алгоритми ніж спрощений підхід із запуском алгоритма пошуку найкоротшого шляху між всіма значимими парами вершин.
Алгоритми
Найважливіші алгоритми для розв'язання цієї задачі:
- Алгоритм Дейкстри розв'язує задачі з однією парою, одним входом і одним виходом.
- Алгоритм Беллмана-Форда розв'язує задачі з одним входом, якщо ваги ребер можуть бути від'ємні.
- Алгоритм пошуку A* розв'язує задачу для однієї пари із використанням евристики в спробі пришвидшити пошук.
- Алгоритм Флойда-Воршелла розв'язує задачу для всіх пар.
- Алгоритм Джонсона розв'язує задачу для всіх пар, і може бути швидшим за алгоритм Флойда-Воршелла на розріджених графах.
- Теорія збурень знаходить (в найгіршому випадку) локально найкоротший шлях.