4430
правок
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей между всеми парами при помощи матричного произведения (посмотреть исходный код)
Версия от 17:24, 17 января 2012
, 17 января 2012нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 27: | Строка 27: | ||
Свидетели могут быть вычислены на первом этапе за время, полилогарифмическое относительно n, по методу, приведенному в [2]. Поддержка свидетелей на втором этапе тривиальна. | Свидетели могут быть вычислены на первом этапе за время, полилогарифмическое относительно n, по методу, приведенному в [2]. Поддержка свидетелей на втором этапе тривиальна. | ||
Если дан ориентированный граф G, стоимости дуг которого задаются целыми числами от 1 до M, где M – целое положительное число, то граф G можно преобразовать в G’, заменив каждую дугу соответствующим количеством дуг единичной стоимости, вплоть до M. Очевидно, что задача для графа G может быть решена путем применения вышеприведенного алгоритма к G’, для чего потребуется время O((Mn)( | Если дан ориентированный граф G, стоимости дуг которого задаются целыми числами от 1 до M, где M – целое положительное число, то граф G можно преобразовать в G’, заменив каждую дугу соответствующим количеством дуг единичной стоимости, вплоть до M. Очевидно, что задача для графа G может быть решена путем применения вышеприведенного алгоритма к G’, для чего потребуется время <math>O((Mn)^{(\omega +3)/2} \, )</math>. Это время оказывается меньше кубического при <math>M < n^{0.116} \, </math>. Поддержка свидетелей вносит дополнительный полилогарифмический коэффициент в каждом случае. | ||
Для неориентированных графов с единичной стоимостью дуги Зейделем было доказано время исполнения | |||
Для неориентированных графов с единичной стоимостью дуги Зейделем было доказано время исполнения <math>\tilde{O}(n^{\omega}) \, </math> [7]. | |||
== Алгоритм Такаоки == | |||
Если стоимости дуг ограничены положительным целым числом M, можно разработать более удачный алгоритм, что было показано Такаокой в [9]. Вкратце рассмотрим алгоритм Романи [6] для произведения матриц расстояния. | Если стоимости дуг ограничены положительным целым числом M, можно разработать более удачный алгоритм, что было показано Такаокой в [9]. Вкратце рассмотрим алгоритм Романи [6] для произведения матриц расстояния. | ||
Пусть A и B – матрицы расстояния формата (n, m) и (m, n), соответственно, элементы которых ограничены числом M либо равны бесконечности. Пусть диагональные элементы равны 0. Преобразуем матрицы A и B в A' и B', где a'ij = (m + l)M-aij, если aij , и 0 в противном случае, а b'ij =(m + 1)M-bij, если bij , и 0 в ином случае. | Пусть A и B – матрицы расстояния формата (n, m) и (m, n), соответственно, элементы которых ограничены числом M либо равны бесконечности. Пусть диагональные элементы равны 0. Преобразуем матрицы A и B в A' и B', где a'ij = (m + l)M-aij, если aij , и 0 в противном случае, а b'ij =(m + 1)M-bij, если bij , и 0 в ином случае. | ||
