4446
правок
Алгоритм поиска кратчайших путей с единственным источником: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей с единственным источником (посмотреть исходный код)
Версия от 22:46, 6 февраля 2018
, 6 февраля 2018нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 32: | Строка 32: | ||
== Применение == | == Применение == | ||
Алгоритмы поиска кратчайших путей часто используются в качестве подпрограмм в других задачах оптимизации, таких как задачи о потоке и паросочетании [ ] и определении местоположения [19]. Широко практикуется такое коммерческое применение алгоритмов нахождения кратчайших путей, как поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps. | Алгоритмы поиска кратчайших путей часто используются в качестве подпрограмм в других задачах оптимизации, таких как задачи о потоке и паросочетании [1] и определении местоположения [19]. Широко практикуется такое коммерческое применение алгоритмов нахождения кратчайших путей, как поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Алгоритм Торупа для решения SSSP-задачи [ ] выполняется за линейное время и потому является оптимальным. Основной задачей остается поиск SSSP-алгоритма с линейным временем выполнения, работающего на ориентированных графах с вещественными | Алгоритм Торупа для решения SSSP-задачи [17] выполняется за линейное время и потому является оптимальным. Основной задачей остается поиск SSSP-алгоритма с линейным временем выполнения, работающего на ''ориентированных'' графах с ''вещественными весам''и ребер. Наилучшее время выполнения для неориентированных графов с вещественными весами ребер приведено в теореме 3. Для ориентированных графов с целыми весами самые быстрые алгоритмы основаны на подходе Дейкстры (а не теореме 2) и выполняются за время <math>O(m \sqrt{log \; log \; n})</math> (рандомизированные) и <math>O(m + n \; log \; log \; n)</math> (детерминированные). | ||
Задача 1. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с целыми весами с временем выполнения O(m)? | ''Задача 1. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с целыми весами с временем выполнения O(m)?'' | ||
Задача 2. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных или неориентированных графов с вещественными весами с временем выполнения O(m) + o( | ''Задача 2. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных или неориентированных графов с вещественными весами с временем выполнения O(m) + o(n log n)?'' | ||
| Строка 46: | Строка 46: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Асано и Имаи [ ], а также Петти и др. оценили эффективность основанных на иерархии SSSP-алгоритмов [14, 17]. Исследования SSSP-алгоритмов на ориентированных графах с целочисленными весами производились неоднократно; наиболее актуальные сведения см. в работе [ ] и ссылках в ней. В последнее время исследователи стремятся найти практичные схемы предварительной обработки, способные очень быстро давать ответы на запрос кратчайших двухточечных путей. Подробнее о недавних работах в этой области – в [3, 11, 16]. | Асано и Имаи [2], а также Петти и др. [15] оценили эффективность основанных на иерархии SSSP-алгоритмов [14, 17]. Исследования SSSP-алгоритмов на ориентированных графах с целочисленными весами производились неоднократно; наиболее актуальные сведения см. в работе [8] и ссылках в ней. В последнее время исследователи стремятся найти практичные схемы предварительной обработки, способные очень быстро давать ответы на запрос кратчайших двухточечных путей. Подробнее о недавних работах в этой области – в [3, 11, 16]. | ||
== Наборы данных == | == Наборы данных == | ||
