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

Обозначим за <math>\delta(i,j) \, </math> кратчайшее расстояние между i и j, а за <math>n(i,j) \, </math> – минимальную длину среди всех кратчайших путей от i до j. Подмножество I множества вершин V является <math>\ell</math>-мостовым множеством, если удовлетворяет следующему условию: если <math>\eta(i,j) \ge \ell</math>, существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math>. I является сильным <math>\ell</math>-мостовым множеством при выполнении условия: если <math>\eta(i,j) \ge \ell \, </math>, то существует <math>k \in I</math>, такое, что <math>\delta(i,j) = \delta(i,k) + \delta(k,j) \, </math> и <math>\eta(i,j) = \eta(i,k) + \eta(k,j) \, </math>. Заметим, что для графа с дугами единичной стоимости эти множества совпадают.

(1) Выберем 9n ln n/ℓ вершин из V случайным образом. В этом случае можно показать, что алгоритм решает задачу нахождения кратчайших путей между всеми парами с высокой вероятностью, т.е. с вероятностью 1 – 1/nc для некоторой константы c > 0; можно показать, что она равна 3. Иными словами, I является сильным ℓ/3—мостовым множеством с высокой вероятностью. Время T в основном определяется произведением (n,m)-Романи. T = Õ(ℓMn((1,r,1)), поскольку элементы матрицы могут иметь величину вплоть до ℓM. Из того, что m = O(n ln n/ℓ) = nr, следует, что ℓ = Õ(n1-r) и, в силу этого, T = O(Mnl-r n((1,r,1)). В случае M = 1 граница на r равна  = 0.575, и, следовательно, T = O(n2.575). Если M = nt  1, время оценивается как О(n2+(t)), где t ≤ 3 –  = 0.624, а  = {t) удовлетворяет равенству (1,,1) = 1 + 2 – t. Это определено из наиболее известного (1,,1) и значения t. Поскольку результат является корректным с высокой вероятностью, этот алгоритм является рандомизированным.

(2) Рассмотрим случай с единичными стоимостями дуг. В варианте (1) вычисление свидетелей производится дополнительно, то есть не является необходимым, если нужны только кратчайшие расстояния. Чтобы получить такую же сложность для точного, а не рандомизированного алгоритма, вычисление свидетелей становится обязательным. Как было отмечено ранее, поддержка свидетелей (то есть матрицы W) вносит дополнительный полилогарифмический коэффициент, что означает, что анализ может быть сосредоточен на произведении Романи в Õ-нотации. Более конкретно, I выбирается в качестве ℓ/3-мостового множества, являющегося сильным при единичной стоимости дуг. Чтобы вычислить I как O(ℓ)-мостовое множество, необходимо получить вершины кратчайшего пути из i в j для каждого i и j, используя матрицу свидетелей W, за время O(ℓ). После получения этих n2 множеств за время O(ℓn2) можно вычислить O(ℓ)-мостовое множество размера O(n ln n/ℓ) с той же временной сложностью, как показано в [10]. Процесс вычисления мостового множества должен остановиться в ℓ = n1/2, поскольку после этой границы процесс становится чрезмерно дорогим; в силу этого после данной границы используется одно и то же мостовое множество. Время вычисления до этой границы остается тем же, что и в варианте (1), а после границы составляет Õ(n2.5). Таким образом, мы получаем алгоритм из двух этапов.