4430
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 14:43, 17 июля 2014
, 17 июля 2014→Алгоритм Алона, Галила и Маргалита
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
== Алгоритм Алона, Галила и Маргалита == | == Алгоритм Алона, Галила и Маргалита == | ||
Полное изложение алгоритма приведено в [1]. Пусть все | Полное изложение алгоритма приведено в [1]. Пусть все ребра графа имеют единичную стоимость. Пусть <math>D^{(\ell)} </math> – <math>\ell </math>-я приближенная матрица для <math>D^* \, </math>, определенная следующим образом: <math>d_{ij}^{(\ell)} = d^*_{ij}</math>, если <math>d^*_{ij} ≤ \ell \, </math>, и <math>d_{ij}^{(\ell)} = \infty \, </math> в противном случае. Пусть A – матрица смежности графа G: <math>a_{ij} = 1 \, </math>, если существует ребро (i, j), и <math>a_{ij} = 0 \, </math> в противном случае. Пусть <math>a_{ii} = 1 \, </math> для всех i. Алгоритм состоит из двух этапов. На первом этапе вычисляются <math>D^{(\ell)} </math> для <math>\ell = 1, ..., r</math> при помощи проверки (i, j)-го элемента <math>A^{\ell} = {a^{\ell}_{ij}}</math>. Заметим, что если <math>a^{\ell} = 1</math>, то существует путь из i в j длиной <math>\ell</math> или меньше. Поскольку булево произведение матриц может быть вычислено за время <math>O(n^{\omega}\, )</math>, время выполнения этого этапа составит <math>O(rn^{\omega}\, )</math>. | ||
На втором этапе алгоритм вычисляет <math>D^{(\ell)} </math> для <math>\ell = r, \mathcal{d} 3/2 r \mathcal{e}, \mathcal{d} 3/2 \mathcal{d} 3/2 r \mathcal{e}\mathcal{e}, ... , n’</math> путем последовательного возведения в квадрат, где n’ – наименьшее целое число в последовательности <math>\ell \,</math>, такое, что <math>\ell \ge n</math>. Пусть <math>T_{i\alpha} = \, </math> {<math>j \mid d_{ij}^{(\ell)} = \alpha</math>} и <math>I_i = T_{i\alpha} \, </math>, такое, что <math>\mid T_{j\alpha}\mid</math> минимально для <math>\mathcal{d} \ell /2 \mathcal{e} < \alpha < \ell</math>. Основное наблюдение второго этапа заключается в следующем: необходимо проверять k только в I<math>_i</math>, размер которого не превышает <math>2n/ \ell \, </math>, поскольку корректные расстояния между <math>\ell + 1 \, </math> и <math>\mathcal{d} 3 \ell/2 \mathcal{e}</math> могут быть получены как суммы <math>d_{ik}^{(\ell)} + d_{kj}^{(\ell)}</math> для некоторых k, удовлетворяющих неравенству <math>\mathcal{d} \ell /2 \mathcal{e} \le d_{ik}^{(\ell)} \le \ell</math>. Значение I<math>_i</math> сходно с I для частичных произведений – за тем исключением, что I меняется для каждого i. Таким образом, время одного возведения в квадрат составляет <math>O(n^3/ \ell \,)</math>; а полное время второго этапа задается при <math>N = \mathcal{d}log_{\frac{3}{2}} n/r\mathcal{e}</math> формулой <math>O(\sum_{s=1}^N n^3/((3/2)^s r) = O(n^3/r)</math>. Сбалансировав оба этапа условием <math>rn^{\omega} = n^3/r \,</math>, получаем время <math>O(n^{(\omega + 3)/2}) = O(n^{2.688}) \,</math> для алгоритма с <math>r = O(n^{(3- \omega)/2}) \, </math>. | На втором этапе алгоритм вычисляет <math>D^{(\ell)} </math> для <math>\ell = r, \mathcal{d} 3/2 r \mathcal{e}, \mathcal{d} 3/2 \mathcal{d} 3/2 r \mathcal{e}\mathcal{e}, ... , n’</math> путем последовательного возведения в квадрат, где n’ – наименьшее целое число в последовательности <math>\ell \,</math>, такое, что <math>\ell \ge n</math>. Пусть <math>T_{i\alpha} = \, </math> {<math>j \mid d_{ij}^{(\ell)} = \alpha</math>} и <math>I_i = T_{i\alpha} \, </math>, такое, что <math>\mid T_{j\alpha}\mid</math> минимально для <math>\mathcal{d} \ell /2 \mathcal{e} < \alpha < \ell</math>. Основное наблюдение второго этапа заключается в следующем: необходимо проверять k только в I<math>_i</math>, размер которого не превышает <math>2n/ \ell \, </math>, поскольку корректные расстояния между <math>\ell + 1 \, </math> и <math>\mathcal{d} 3 \ell/2 \mathcal{e}</math> могут быть получены как суммы <math>d_{ik}^{(\ell)} + d_{kj}^{(\ell)}</math> для некоторых k, удовлетворяющих неравенству <math>\mathcal{d} \ell /2 \mathcal{e} \le d_{ik}^{(\ell)} \le \ell</math>. Значение I<math>_i</math> сходно с I для частичных произведений – за тем исключением, что I меняется для каждого i. Таким образом, время одного возведения в квадрат составляет <math>O(n^3/ \ell \,)</math>; а полное время второго этапа задается при <math>N = \mathcal{d}log_{\frac{3}{2}} n/r\mathcal{e}</math> формулой <math>O(\sum_{s=1}^N n^3/((3/2)^s r) = O(n^3/r)</math>. Сбалансировав оба этапа условием <math>rn^{\omega} = n^3/r \,</math>, получаем время <math>O(n^{(\omega + 3)/2}) = O(n^{2.688}) \,</math> для алгоритма с <math>r = O(n^{(3- \omega)/2}) \, </math>. | ||
Свидетели могут быть вычислены на первом этапе за время, полилогарифмическое относительно n, по методу, приведенному в [2]. Поддержка свидетелей на втором этапе тривиальна. | Свидетели могут быть вычислены на первом этапе за время, полилогарифмическое относительно n, по методу, приведенному в [2]. Поддержка свидетелей на втором этапе тривиальна. | ||
Если дан ориентированный граф G, стоимости | Если дан ориентированный граф G, стоимости ребер которого задаются целыми числами от 1 до M, где M – целое положительное число, то граф G можно преобразовать в G’, заменив каждое ребро соответствующим количеством ребер единичной стоимости, вплоть до M. Очевидно, что задача для графа G может быть решена путем применения вышеприведенного алгоритма к G’, для чего потребуется время <math>O((Mn)^{(\omega +3)/2} \, )</math>. Это время оказывается меньше кубического при <math>M < n^{0.116} \, </math>. Поддержка свидетелей вносит дополнительный полилогарифмический коэффициент в каждом случае. | ||
Для неориентированных графов с единичной стоимостью | Для неориентированных графов с единичной стоимостью ребра Зейделем было доказано время исполнения <math>\tilde{O}(n^{\omega}) \, </math> [7]. | ||
== Алгоритм Такаоки == | == Алгоритм Такаоки == | ||
