4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 14:08, 17 января 2012
, 17 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 24: | Строка 24: | ||
Полное изложение алгоритма приведено в [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>. | Полное изложение алгоритма приведено в [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. Таким образом, время одного возведения в квадрат составляет O( | На втором этапе алгоритм вычисляет <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]. Поддержка свидетелей на втором этапе тривиальна. | ||