Алгоритм Зайдельса - Википедия - Seidels algorithm

Алгоритм Зейделя алгоритм, разработанный Раймунд Зайдель в 1992 году для задача поиска всех пар кратчайшего пути для неориентированных, невзвешенных, связанных графов.^[1] Решает проблему в ${ Displaystyle O (V ^ { omega} log V)}$ ожидаемое время для графика с ${ displaystyle V}$ вершины, где ${ displaystyle omega <2.373}$ - показатель сложности ${ Displaystyle О (п ^ { omega})}$ из ${ Displaystyle п раз п}$ матричное умножение. Если искать только расстояния между каждой парой вершин, в худшем случае может быть достигнута такая же граница времени. Несмотря на то, что алгоритм разработан для связанных графов, его можно применять индивидуально к каждому. связный компонент графика с одинаковым временем работы в целом. Существует исключение из указанного выше ожидаемого времени выполнения для вычисления путей: если ${ displaystyle omega = 2}$ ожидаемое время работы становится ${ Displaystyle О (V ^ {2} log ^ {2} V)}$.

Детали реализации

Ядром алгоритма является процедура, вычисляющая длину кратчайших путей между любой парой вершин. ${ Displaystyle O (V ^ { omega} log V)}$ время в худшем случае. После того, как длины вычислены, пути могут быть восстановлены с помощью Алгоритм Лас-Вегаса ожидаемое время работы ${ Displaystyle O (V ^ { omega} log V)}$ за ${ displaystyle omega> 2}$ и ${ Displaystyle О (V ^ {2} log ^ {2} V)}$ за ${ displaystyle omega = 2}$.

Вычисление длин кратчайших путей

В приведенном ниже коде Python предполагается, что входной граф задан как ${ Displaystyle п раз п}$ ${ displaystyle 0}$-${ displaystyle 1}$ матрица смежности ${ displaystyle A}$ с нулями по диагонали. Он определяет функцию APD, которая возвращает матрицу с записями ${ displaystyle D_ {i, j}}$ такой, что ${ displaystyle D_ {i, j}}$ это длина кратчайшего пути между вершинами ${ displaystyle i}$ и ${ displaystyle j}$. Используемый матричный класс может быть любой реализацией матричного класса, поддерживающей операторы умножения, возведения в степень и индексирования (например, numpy.matrix ).

def apd(А, п: int):    "" "Вычислить длины кратчайших путей." ""    если все(А[я][j] за я в классифицировать(п) за j в классифицировать(п) если я != j):        возвращаться А    Z = А ** 2    B = матрица([        [1 если я != j и (А[я][j] == 1 или же Z[я][j] > 0) еще 0 за j в классифицировать(п)]    за я в классифицировать(п)])    Т = apd(B, п)    Икс = Т*А    степень = [сумма(А[я][j] за j в классифицировать(п)) за я в классифицировать(п)]    D = матрица([        [2 * Т[я][j] если Икс[я][j] >= Т[я][j] * степень[j] еще 2 * Т[я][j] - 1 за j в классифицировать(п)]    за я в классифицировать(п)])    возвращаться D

В базовом случае проверяется, описывает ли входная матрица смежности полный граф, и в этом случае все кратчайшие пути имеют длину ${ displaystyle 1}$.

Графы с весами из конечных вселенных

Алгоритмы для неориентированных и ориентированных графов с весами из конечной вселенной ${ Displaystyle {1, ldots, М, + infty }}$ тоже существуют. Самый известный алгоритм для направленного случая - вовремя ${ Displaystyle { тильда {O}} (M ^ {1 / (4- omega)} V ^ {2 + 1 / (4- omega)})}$ Цвиком в 1998 году.^[2] Этот алгоритм использует умножение прямоугольной матрицы вместо умножения квадратной матрицы. Лучшие верхние границы можно получить, если использовать лучший из имеющихся алгоритмов умножения прямоугольных матриц вместо достижения прямоугольного умножения с помощью умножения нескольких квадратных матриц. Самый известный алгоритм для неориентированного случая вовремя ${ displaystyle { tilde {O}} (MV ^ { omega})}$ Шошаном и Цвиком в 1999 году.^[3] Первоначальная реализация этого алгоритма была ошибочной и была исправлена ​​Эйринакисом, Уильямсоном и Субрамани в 2016 году.^[4]

Примечания