Программные продукты и системы

Задача поиска кратчайшего пути в графе (Shortest-Paths, SP) – хорошо известная задача теории графов, имеющая многие реальные приложения, такие как планирование маршрута в веб-структурах, навигационные системы, моделирование трафика, логистическая оптимизация. Задача SP состоит в поиске кратчайшего пути в заданном графе между двумя его вершинами s и t (стартовой и целевой соответственно), в котором минимизируется сумма длин ребер, составляющих (s, t)-путь. Существует много классических алгоритмов решения задачи SP. Самый известный из них – алгоритм Дейкстры, который равномерно расширяет пространство поиска решения, начиная от стартовой вершины s и далее последовательно до целевой вершины t, присваивает каждой пройденной вершине v временную метку – верхнюю оценку кратчайшего (s, v)-пути, и превращает временную метку в постоянную, когда ее значение совпадает с кратчайшим (s, v)-путем. Алгоритм A* добавляет в алгоритм Дейкстры потенциальную функцию, которая оценивает снизу кратчайший (v, t)-путь. Данные алгоритмы находят точное решение задачи SP за полиномиальное время.

Во многих случаях требуется вычислить за несколько секунд кратчайший (s, t)-путь в графе большой размерности. Типичным примером является поиск кратчайшего маршрута в дорожной сети, насчитывающей несколько десятков или сотен тысяч узлов. В этих условиях классические алгоритмы начинают работать неприемлемо долго. Чтобы справиться с этой проблемой, используют различные приемы ускорения. Большинство этих приемов основаны на двухфазном подходе решения задачи SP, который содержит фазу предобработки и фазу выполнения (s, t)-запроса – запроса на вычисление (s, t)-пути в исходном графе.

Подробное описание дается в статье «Адаптивное размещение ориентиров в задаче о кратчайшем пути для графов большой размерности», авторы: Быкова В.В., Солдатенко А.А.(Сибирский федеральный университет, Красноярск).