Алгоритм поиска кратчайших путей с единственным источником: различия между версиями

Алгоритмы поиска кратчайших путей часто используются в качестве подпрограмм в других задачах оптимизации, таких как задачи о потоке и паросочетании [ ] и определении местоположения [19]. Широко практикуется такое коммерческое применение алгоритмов нахождения кратчайших путей, как поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps.

Алгоритм Торупа для решения SSSP-задачи [ ] выполняется за линейное время и потому является оптимальным. Основной задачей остается поиск SSSP-алгоритма с линейным временем выполнения, работающего на ориентированных графах с вещественными весами ребер. Наилучшее время выполнения для неориентированных графов с вещественными весами ребер приведено в теореме 3. Для ориентированных графов с целыми весами самые быстрые алгоритмы основаны на подходе Дейкстры (а не теореме 2) и выполняются за время O(mploglogn) (рандомизированные) и O(m + n log log n) (детерминированные).

Задача 1. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с целыми весами с временем выполнения O(m)?

Задача 2. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных или неориентированных графов с вещественными весами с временем выполнения O(m) + o(nlogn)?

Асано и Имаи [ ], а также Петти и др. оценили эффективность основанных на иерархии SSSP-алгоритмов [14, 17]. Исследования SSSP-алгоритмов на ориентированных графах с целочисленными весами производились неоднократно; наиболее актуальные сведения см. в работе [ ] и ссылках в ней. В последнее время исследователи стремятся найти практичные схемы предварительной обработки, способные очень быстро давать ответы на запрос кратчайших двухточечных путей. Подробнее о недавних работах в этой области – в [3, 11, 16].