4501
правка
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 13:05, 17 января 2012
, 17 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 24: | Строка 24: | ||
Полное изложение алгоритма приведено в [1]. Пусть все дуги графа имеют единичную стоимость. Пусть <math>D^{(\ell)} </math> – ℓ-я приближенная матрица для <math>D^* \, </math>, определенная следующим образом: <math>d_{ij}^{(\ell)} = d^*_{ij}</math>, если <math>d^*_{ij} ≤ ℓ \, </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> для ℓ= 1, ..., r при помощи проверки (i, j)-го элемента <math>A^{\ell} = {a^{\ell}_{ij}}</math>. Заметим, что если <math>a^{\ell} </math> = 1, то существует путь из i в j длиной ℓ или меньше. Поскольку булево произведение матриц может быть вычислено за время <math>O(n^{\omega}\, )</math>, время выполнения этого этапа составит <math>O(rn^{\omega}\, )</math>. | Полное изложение алгоритма приведено в [1]. Пусть все дуги графа имеют единичную стоимость. Пусть <math>D^{(\ell)} </math> – ℓ-я приближенная матрица для <math>D^* \, </math>, определенная следующим образом: <math>d_{ij}^{(\ell)} = d^*_{ij}</math>, если <math>d^*_{ij} ≤ ℓ \, </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> для ℓ= 1, ..., r при помощи проверки (i, j)-го элемента <math>A^{\ell} = {a^{\ell}_{ij}}</math>. Заметим, что если <math>a^{\ell} </math> = 1, то существует путь из i в j длиной ℓ или меньше. Поскольку булево произведение матриц может быть вычислено за время <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>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 только в Ii, размер которого не превышает 2n/ℓ, поскольку корректные расстояния между ℓ + 1 и 3ℓ/2 могут быть получены как суммы d(ℓ)ik + d(ℓ)kj для некоторых k, удовлетворяющих неравенству ℓ/2 ≤ d(ℓ)ik ≤ ℓ. Значение Ii сходно с I для частичных произведений – за тем исключением, что I меняется для каждого i. Таким образом, время одного возведения в квадрат составляет O(n3/ℓ); а полное время второго этапа задается при N = log3/2 n/r формулой . Сбалансировав оба этапа условием 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. Поддержка свидетелей вносит дополнительный полилогарифмический коэффициент в каждом случае. | ||