4488
правок
Irina (обсуждение | вклад) м (Irina переименовал страницу Алгоритм поиска кратчайших путей в разреженных графах в [[Алгоритм поиска кратчайших путей между всеми парам…) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 8: | Строка 8: | ||
== Классические алгоритмы == | == Классические алгоритмы == | ||
Алгоритм Беллмана-Форда решает задачу нахождения кратчайшего пути с единственным источником за время O(mn) в предположении, что длины дуг неотрицательны; алгоритм Дейкстры решает ее за время O(m + nlog n). Существует широко известное преобразование с сохранением кратчайших путей и временем | Алгоритм Беллмана-Форда решает задачу нахождения кратчайшего пути с единственным источником за время O(mn) в предположении, что длины дуг неотрицательны; алгоритм Дейкстры решает ее за время O(m + nlog n). Существует широко известное преобразование с сохранением кратчайших путей и временем выполнения O(mn), заменяющее любую функцию длины на неотрицательную функцию длины. Используя это преобразование и n проходов алгоритма Дейкстры, получаем алгоритм нахождения кратчайшего пути между всеми парами с временем выполнения <math>O(mn + n^2 log n) = O(n^3)</math>. Алгоритм Флойда-Уоршелла вычисляет кратчайший путь между всеми парами более прямолинейным способом и за время <math>O(n^3)</math>. Описание этих алгоритмов можно найти в [4]. Известно, что поиск кратчайшего пути между всеми парами является асимптотически эквивалентным матричному умножению (min; +) [1], которое поддается вычислению при помощи неравномерного алгоритма, выполняющего <math>O(n^{2.5})</math> числовых операций [6]. (Наиболее быстрый известный матричный умножитель (min; +) выполняется за время <math>O(n^3(log log n)^3/(log n)^2)</math> [3]). | ||
== Графы с целочисленными весами == | == Графы с целочисленными весами == | ||
Наиболее современные исследования проблемы кратчайших путей предполагают, что длины дуг являются целыми числами в диапазоне {–C, ..., C} либо {0, ..., C}. Одно из направлений сводит поиск кратчайшего пути между всеми парами к серии стандартных операций матричного умножения. Применимость этих алгоритмов ограничена, поскольку время | Наиболее современные исследования проблемы кратчайших путей предполагают, что длины дуг являются целыми числами в диапазоне {–C, ..., C} либо {0, ..., C}. Одно из направлений сводит поиск кратчайшего пути между всеми парами к серии стандартных операций матричного умножения. Применимость этих алгоритмов ограничена, поскольку время выполнения линейно растет пропорционально C. Существуют более быстрые алгоритмы для поиска кратчайшего пути с единственным источником как для неотрицательных длин дуг, так и для произвольных длин дуг. Первые задействуют мощь оперативной памяти, проводя сортировку за время o(n log n); вторые основываются на технике [[масштабирование|масштабирования]]. Цвик [19] приводит обзор алгоритмов нахождения кратчайших путей вплоть до 2001 года. | ||
== Основные результаты == | == Основные результаты == | ||
Алгоритм Петти для поиска кратчайших путей между всеми парами [13] адаптирует [[иерархия|иерархический подход]] Торупа [17] (разработанный для неориентированных графов с целочисленными весами) для ориентированных графов с действительными весами. Теорема 1 описывает первое улучшение времени | Алгоритм Петти для поиска кратчайших путей между всеми парами [13] адаптирует [[иерархия|иерархический подход]] Торупа [17] (разработанный для неориентированных графов с целочисленными весами) для ориентированных графов с действительными весами. Теорема 1 описывает первое улучшение времени выполнения по сравнению с <math>O(mn + n^2 log n)</math> алгоритма Дейкстры для произвольных графов с действительными весами. | ||
'''Теорема 1. Пусть имеется ориентированный граф с действительными весами. Кратчайшие пути между всеми парами могут быть найдены за время <math>O(mn + n^2 loglog n)</math>. | '''Теорема 1. Пусть имеется ориентированный граф с действительными весами. Кратчайшие пути между всеми парами могут быть найдены за время <math>O(mn + n^2 loglog n)</math>. | ||
''' | ''' | ||
Этот алгоритм достигает логарифмического ускорения благодаря применению трех новых техник. Первая заключается в использовании неизбежного сходства между кратчайшими путями с единственным источником, исходящими из расположенных неподалеку вершин. Вторая представляет собой метод вычисления дискретных приближенных расстояний в графах с действительными весами. Третьей техникой является новый алгоритм иерархического типа для нахождения кратчайших путей с единственным источником, который при наличии приближенных расстояний достаточной точности | Этот алгоритм достигает логарифмического ускорения благодаря применению трех новых техник. Первая заключается в использовании неизбежного сходства между кратчайшими путями с единственным источником, исходящими из расположенных неподалеку вершин. Вторая представляет собой метод вычисления дискретных приближенных расстояний в графах с действительными весами. Третьей техникой является новый алгоритм иерархического типа для нахождения кратчайших путей с единственным источником, который при наличии приближенных расстояний достаточной точности выполняется за время O(m + n log log n). | ||
Строка 31: | Строка 31: | ||
''' | ''' | ||
Второй результат исследований [13, 15] гласит, что не существует алгоритма иерархического типа для поиска кратчайших путей, время | Второй результат исследований [13, 15] гласит, что не существует алгоритма иерархического типа для поиска кратчайших путей, время выполнения которого было бы лучше, чем O(m + n log n)алгоритма Дейкстры. | ||
Строка 45: | Строка 45: | ||
'''Проблема 1'''. Существует ли алгоритм поиска кратчайших путей с единственным источником или двухточечный алгоритм для произвольных взвешенных графов с временем o(mn)? | '''Проблема 1'''. Существует ли алгоритм поиска кратчайших путей с единственным источником или двухточечный алгоритм для произвольных взвешенных графов с временем o(mn)? | ||
'''Проблема 2'''. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с неотрицательными весами с временем | '''Проблема 2'''. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с неотрицательными весами с временем выполнения O(m) + o(n log n)? Существует ли он для неориентированных графов? | ||
Строка 53: | Строка 53: | ||
'''Проблема 3'''. Является ли двухточечный алгоритм поиска кратчайших путей более простым, чем алгоритм поиска кратчайших путей между всеми парами, на произвольных взвешенных графах? | '''Проблема 3'''. Является ли двухточечный алгоритм поиска кратчайших путей более простым, чем алгоритм поиска кратчайших путей между всеми парами, на произвольных взвешенных графах? | ||
'''Проблема 4'''. Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической, т.е. меньше <math>O(n^{3 - \epsilon}) \, </math>?Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической для графов с целочисленными весами со слабой зависимостью от наибольшего веса дуги C, т.е. | '''Проблема 4'''. Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической, т.е. меньше <math>O(n^{3 - \epsilon}) \, </math>?Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической для графов с целочисленными весами со слабой зависимостью от наибольшего веса дуги C, т. е. выполняющийся за время <math>O(n^{3 - \epsilon} polylog(C)) \, </math>? | ||
правок