Задача про найкоротший шлях

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
(6, 4, 5, 1) і (6, 4, 3, 2, 1) є шляхами між вершинами 6 і 1
Найкоротший шлях (A, C, E, D, F) між вершинами A та F у зваженому орієнтованому графі

В теорії графів, задача про найкоротший шлях полягає в знаходженні такого шляху між двома вершинами (або вузлами) графу, що сума ваг ребер з яких він складається мінімальна. Прикладом може бути знаходження найкоротшого шляху між двома пунктами на дорожній мапі; в цьому випадку, вершинами є пункти, а ребрами - відтинки дороги із вагами, рівними часу, необхідному для подолання цього відтинку.

Формально, маємо зважений граф (це набір вершин V і ребер E з дійсно-значимою функцією ваги f : E → R), і заданим елементом v з V, знайти шлях P з v до v' з V такий, що

\sum_{p\in P} f(p)

найменша серед усіх шляхів, що зв'язують v з v' .

Така задача іноді згадується як Задача про найкоротший шлях між парою вершин, щоб відрізнити від наступних узагальнень:

  • Задача про найкоротші шляхи з одного входом, тут ми маємо знайти найкоротші шляхи між вхідною вершиною v та всіма іншими вершинами графа.
  • Задача про найкоротші шляхи з одним виходом, тут ми маємо знайти найкоротші шляхи з усіх вершин графа до однієї вихідної v. Може бути зведена до задачі з одним входом шляхом зміни на зворотні ребер графа.
  • Задача про найкоротші шляхи для всіх пар, тут ми маємо знайти найкоротші шляхи між кожною парою вершин v, v' в графі.

Ці узагальнення мають значно дієвіші алгоритми ніж спрощений підхід із запуском алгоритма пошуку найкоротшого шляху між всіма значимими парами вершин.

Алгоритми[ред.ред. код]

Найважливіші алгоритми для розв'язання цієї задачі:

Див. також[ред.ред. код]