Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями

Полное изложение алгоритма приведено в [1]. Пусть все дуги графа имеют единичную стоимость. Пусть <math>D^{(\ell)} </math> – ℓ-я приближенная матрица для D*, определенная следующим образом: d(ℓ)ij = d*ij, если d*ij ≤ ℓ, и d(ℓ)ij =  в противном случае. Пусть A – матрица смежности графа G: <math>a_{ij} \, </math> = 1, если существует дуга (i, j), и <math>a_{ij} \, </math> = 0 в противном случае. Пусть <math>a_{ii} \, </math> = 1 для всех i. Алгоритм состоит из двух этапов. На первом этапе вычисляются D(ℓ) для ℓ= 1, ..., r при помощи проверки (i, j)-го элемента Aℓ = {aℓij}. Заметим, что если aℓ = 1, то существует путь из i в j длиной ℓ или меньше. Поскольку булево произведение матриц может быть вычислено за время O(n), время выполнения этого этапа составит O(rn).

На втором этапе алгоритм вычисляет D(ℓ) для ℓ = 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).