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

Пусть дан ориентированный граф G = (V, E), где V = {1, ..., n} – множество вершин, а E – множество дуг. Стоимость дуги (i, j) <math>\in</math> E обозначается как <math>d_{ij}\, </math>. Матрица D размера <math>n \times n</math> содержит элемент <math>d_{ij}\, </math> в позиции (i, j). Для простоты предположим, что <math>d_{ij} > 0 \, </math> и <math>d_{ii} = 0 \, </math> для всех <math>i \ne j</math>. Если не существует дуги из i в j, положим <math>d_{ij} = \infty</math>. Стоимость, или расстояние, пути представляет собой сумму стоимостей всех дуг на пути. Длина пути равна количеству дуг на пути. Кратчайшее расстояние между вершинами i и j равняется минимальной стоимости среди всех путей, ведущих от i до j, и обозначается как <math>d_{ij}^*</math>. Пусть <math>D^* = {d_{ij}^*}</math>. Значение n называется размером матрицы.

Полное изложение алгоритма приведено в [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>I_i \, </math>, размер которого не превышает <math>2n/ \ell \, </math>, поскольку корректные расстояния между ℓ + 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).