Seidel's algorithm is an algorithm designed by
Raimund Seidel
Raimund G. Seidel is a German and Austrian theoretical computer scientist and an expert in computational geometry.
Seidel was born in Graz, Austria, and studied with Hermann Maurer at the Graz University of Technology. He earned his M.Sc. in 1 ...
in 1992 for the
all-pairs-shortest-path problem for undirected, unweighted, connected graphs.
It solves the problem in
expected time for a graph with
vertices, where
is the exponent in the complexity
of
matrix multiplication
In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix (mathematics), matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the n ...
. If only the distances between each pair of vertices are sought, the same time bound can be achieved in the worst case. Even though the algorithm is designed for connected graphs, it can be applied individually to each
connected component of a graph with the same running time overall. There is an exception to the expected running time given above for computing the paths: if
the expected running time becomes
.
Details of the implementation
The core of the algorithm is a procedure that computes the length of the shortest-paths between any pair of vertices.
In the worst case this can be done in
time. Once the lengths are computed, the paths can be reconstructed using a
Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives Correctness (computer science), correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas alg ...
whose expected running time is
for
and
for
.
Computing the shortest-paths lengths
The Python code below assumes the input graph is given as a
-
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
with zeros on the diagonal. It defines the function APD which returns a matrix with entries
such that
is the length of the shortest path between the vertices
and
. The matrix class used can be any matrix class implementation supporting the multiplication, exponentiation, and indexing operators (for exampl
numpy.matrix.
def apd(A, n: int):
"""Compute the shortest-paths lengths."""
if all(A j] for i in range(n) for j in range(n) if i != j):
return A
Z = A**2
B = matrix(
j"> [1 if i != j and (A j 1 or Z j] > 0) else 0 for j in range(n)]
for i in range(n)
]
)
T = apd(B, n)
X = T * A
degree = [sum(A j] for j in range(n)) for i in range(n)]
D = matrix(
j"> [
2 * T jif X j] >= T j] * degree[j] else 2 * T j] - 1
for j in range(n)
]
for i in range(n)
]
)
return D
The base case tests whether the input adjacency matrix describes a complete graph, in which case all shortest paths have length
.
Graphs with weights from finite universes
Algorithms for undirected and directed graphs with weights from a finite universe
also exist. The best known algorithm for the directed case is in time
by Zwick in 1998. This algorithm uses rectangular matrix multiplication instead of square matrix multiplication. Better upper bounds can be obtained if one uses the best rectangular matrix multiplication algorithm available instead of achieving rectangular multiplication via multiple square matrix multiplications. The best known algorithm for the undirected case is in time
by Shoshan and Zwick in 1999. The original implementation of this algorithm was erroneous and has been corrected by Eirinakis, Williamson, and Subramani in 2016.
Notes
{{reflist, 1
Graph algorithms
Polynomial-time problems
Computational problems in graph theory
Articles with example Python (programming language) code
Graph distance