Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 17: | Строка 17: | ||
Лучший алгоритм [3] вычисляет произведение (1) за время <math>O(n^ \omega) \, </math>, где <math>\omega \, </math> = 2.376. Далее мы будем учитывать три знака после запятой. Для вычисления произведения (2) булевы значения 0 и 1 в матрицах A и B можно рассматривать как целые числа, применить алгоритм для вычисления (1) и затем заменить ненулевые элементы получившейся матрицы на 1. Следовательно, его сложность также равна <math>O(n^ \omega) \, </math>. ''Свидетели'' произведения (2) задаются матрицей свидетелей <math>W = {w_{ij}} \, </math>, где <math>w_{ij} = k \, </math> для некоторого k, такого, что <math>a_{ik} \wedge b_{kj} = 1</math>. Если такого k не существует, <math>w_{ij} = 0 \, </math>. ''Матрица свидетелей'' <math>W = w_{ij} \, </math> для (3) определяется следующим образом: <math>w_{ij} = k \, </math>, при котором значение <math>c_{ij} \,</math> минимально. Если существует алгоритм для (3) с временем T(n), игнорирующий полилогарифмический коэффициент n, задача поиска кратчайших путей между всеми парами может быть решена за время Õ(T(n)) путем последовательного применения метода возведения в квадрат, заключающегося в повторном выполнении D | Лучший алгоритм [3] вычисляет произведение (1) за время <math>O(n^ \omega) \, </math>, где <math>\omega \, </math> = 2.376. Далее мы будем учитывать три знака после запятой. Для вычисления произведения (2) булевы значения 0 и 1 в матрицах A и B можно рассматривать как целые числа, применить алгоритм для вычисления (1) и затем заменить ненулевые элементы получившейся матрицы на 1. Следовательно, его сложность также равна <math>O(n^ \omega) \, </math>. ''Свидетели'' произведения (2) задаются матрицей свидетелей <math>W = {w_{ij}} \, </math>, где <math>w_{ij} = k \, </math> для некоторого k, такого, что <math>a_{ik} \wedge b_{kj} = 1</math>. Если такого k не существует, <math>w_{ij} = 0 \, </math>. ''Матрица свидетелей'' <math>W = w_{ij} \, </math> для (3) определяется следующим образом: <math>w_{ij} = k \, </math>, при котором значение <math>c_{ij} \,</math> минимально. Если существует алгоритм для (3) с временем T(n), игнорирующий полилогарифмический коэффициент n, задача поиска кратчайших путей между всеми парами может быть решена за время Õ(T(n)) путем последовательного применения метода возведения в квадрат, заключающегося в повторном выполнении <math>D \leftarrow D \times D</math> <math>O(\log n) \,</math> раз. | ||
Вычисление кратчайших путей будет здесь определяться как нахождение матрицы свидетелей размера n, которой может задаваться кратчайший путь из i в j, за время O(ℓ), где ℓ – длина пути. Более точно, если wij = k в матрице свидетелей W = {wij}, это означает, что путь из i в j проходит через k. Таким образом, рекурсивная функция path(i,j) задается равной (path(i,k),k, path(k, j)), если wij = k> 0, и nil в случае wij = 0, когда путь определяется списком вершин, исключая конечные точки. В дальнейшем изложении k будет записываться в wij в тех случаях, когда будет найден такой элемент k, что путь из i в j модифицируется или задается заново путями из i в k и из k в j. Предшествующие результаты приводятся в качестве схемы получения основных результатов. | Вычисление кратчайших путей будет здесь определяться как нахождение матрицы свидетелей размера n, которой может задаваться кратчайший путь из i в j, за время O(ℓ), где ℓ – длина пути. Более точно, если wij = k в матрице свидетелей W = {wij}, это означает, что путь из i в j проходит через k. Таким образом, рекурсивная функция path(i,j) задается равной (path(i,k),k, path(k, j)), если wij = k> 0, и nil в случае wij = 0, когда путь определяется списком вершин, исключая конечные точки. В дальнейшем изложении k будет записываться в wij в тех случаях, когда будет найден такой элемент k, что путь из i в j модифицируется или задается заново путями из i в k и из k в j. Предшествующие результаты приводятся в качестве схемы получения основных результатов. | ||