4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 13:21, 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 только в <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(n3/ℓ); а полное время второго этапа задается при N = \mathcal{d}log3/2 n/r\mathcal{e} формулой . Сбалансировав оба этапа условием rn = n3/r, получаем время O(n(+3)/2) = O(n2.688) для алгоритма с r = О(n(3-)/2). | ||
Свидетели могут быть вычислены на первом этапе за время, полилогарифмическое относительно n, по методу, приведенному в [2]. Поддержка свидетелей на втором этапе тривиальна. | Свидетели могут быть вычислены на первом этапе за время, полилогарифмическое относительно n, по методу, приведенному в [2]. Поддержка свидетелей на втором этапе тривиальна. | ||
Если дан ориентированный граф G, стоимости дуг которого задаются целыми числами от 1 до M, где M – целое положительное число, то граф G можно преобразовать в G’, заменив каждую дугу соответствующим количеством дуг единичной стоимости, вплоть до M. Очевидно, что задача для графа G может быть решена путем применения вышеприведенного алгоритма к G’, для чего потребуется время O((Mn)(+3)/2). Это время оказывается меньше кубического при M < n0.116. Поддержка свидетелей вносит дополнительный полилогарифмический коэффициент в каждом случае. | Если дан ориентированный граф G, стоимости дуг которого задаются целыми числами от 1 до M, где M – целое положительное число, то граф G можно преобразовать в G’, заменив каждую дугу соответствующим количеством дуг единичной стоимости, вплоть до M. Очевидно, что задача для графа G может быть решена путем применения вышеприведенного алгоритма к G’, для чего потребуется время O((Mn)(+3)/2). Это время оказывается меньше кубического при M < n0.116. Поддержка свидетелей вносит дополнительный полилогарифмический коэффициент в каждом случае. | ||