Алгоритм Зейделя

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

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

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

def  apd ( A ,  n :  int ): """Вычислить длины кратчайших путей.""" if all ( A [ i ][ j ] for i in range ( n ) for j in range ( n ) if i != j ): return A Z = A ** 2 B = matrix ( [ [ 1 if i != j and ( A [ i ][ j ] == 1 or Z [ i ][ j ] > 0 ) else 0 for j in range ( n )] for i in range ( n ) ] ) T = apd ( B , n ) X = T * A degree = [ sum ( A [ i ][ j ] for j in range ( n )) for i in range ( n )] D = matrix ( [ [ 2 * T [ i ][ j ] if X [ i ][ j ] >= T [ i ][ j ] * degree [ j ] else 2 * T [ i ][ j ] - 1 для j в диапазоне ( n ) ] для i в диапазоне ( n ) ] ) вернуть D                                                                                                      

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

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