4430
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 12:45, 17 января 2012
, 17 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 22: | Строка 22: | ||
== Алгоритм Алона, Галила и Маргалита == | == Алгоритм Алона, Галила и Маргалита == | ||
Полное изложение алгоритма приведено в [1]. Пусть все дуги графа имеют единичную стоимость. Пусть <math>D^{(\ell)} </math> – ℓ-я приближенная матрица для <math>D^* \, </math>, определенная следующим образом: <math>d_{ij}^{(\ell)} = d^*_{ij}</math>, если d*ij ≤ ℓ, и | Полное изложение алгоритма приведено в [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 длиной ℓ или меньше. Поскольку булево произведение матриц может быть вычислено за время O(n), время выполнения этого этапа составит O(rn). | ||
На втором этапе алгоритм вычисляет <math>D^{(\ell)} </math> для ℓ = r, 3/2 r, 3/2 3/2 r, ... , n’ путем последовательного возведения в квадрат, где n’ – наименьшее целое число в последовательности ℓ, такое, что ℓ n. Пусть Tiα = {j d(ℓ)ij = α} и Ii = Tiα, такое, что Tja минимально для ℓ/2 < α < ℓ. Основное наблюдение второго этапа заключается в следующем: необходимо проверять 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). | На втором этапе алгоритм вычисляет <math>D^{(\ell)} </math> для ℓ = r, 3/2 r, 3/2 3/2 r, ... , n’ путем последовательного возведения в квадрат, где n’ – наименьшее целое число в последовательности ℓ, такое, что ℓ n. Пусть Tiα = {j d(ℓ)ij = α} и Ii = Tiα, такое, что Tja минимально для ℓ/2 < α < ℓ. Основное наблюдение второго этапа заключается в следующем: необходимо проверять 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). | ||
