Seidel's algorithm

<h2 id="details-of-the-implementation">Details of the implementation</h2>
<p>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 
  
    
      
        O
        (
        
          V
          
            ω
          
        
        log
        ⁡
        V
        )
      
    
    {\displaystyle O(V^{\omega }\log V)}
  
 time. Once the lengths are computed, the paths can be reconstructed using a <a href="/facts/Las_Vegas_algorithm/K43MRwQz">Las Vegas algorithm</a> whose expected running time is 
  
    
      
        O
        (
        
          V
          
            ω
          
        
        log
        ⁡
        V
        )
      
    
    {\displaystyle O(V^{\omega }\log V)}
  
 for 
  
    
      
        ω
        >
        2
      
    
    {\displaystyle \omega >2}
  
 and 
  
    
      
        O
        (
        
          V
          
            2
          
        
        
          log
          
            2
          
        
        ⁡
        V
        )
      
    
    {\displaystyle O(V^{2}\log ^{2}V)}
  
 for 
  
    
      
        ω
        =
        2
      
    
    {\displaystyle \omega =2}
  
.
</p>
<h3>Computing the shortest-paths lengths</h3>
<p>The Python code below assumes the input graph is given as a 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 
  
    
      
        0
      
    
    {\displaystyle 0}
  
-
  
    
      
        1
      
    
    {\displaystyle 1}
  
 <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> 
  
    
      
        A
      
    
    {\displaystyle A}
  
 with zeros on the diagonal. It defines the function APD which returns a matrix with entries 
  
    
      
        
          D
          
            i
            ,
            j
          
        
      
    
    {\displaystyle D_{i,j}}
  
 such that 
  
    
      
        
          D
          
            i
            ,
            j
          
        
      
    
    {\displaystyle D_{i,j}}
  
 is the length of the shortest path between the vertices 
  
    
      
        i
      
    
    {\displaystyle i}
  
 and 
  
    
      
        j
      
    
    {\displaystyle j}
  
. The matrix class used can be any matrix class implementation supporting the multiplication, exponentiation, and indexing operators (for example <a href="https://docs.scipy.org/doc/numpy/reference/generated/numpy.matrix.html">numpy.matrix</a>).
</p>
def apd(A, n: int):
    """Compute the shortest-paths lengths."""
    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
                for j in range(n)
            ]
            for i in range(n)
        ]
    )
    return D

<p>The base case tests whether the input adjacency matrix describes a complete graph, in which case all shortest paths have length 
  
    
      
        1
      
    
    {\displaystyle 1}
  
.
</p>
<h2 id="graphs-with-weights-from-finite-universes">Graphs with weights from finite universes</h2>
<p>Algorithms for undirected and directed graphs with weights from a finite universe 
  
    
      
        {
        1
        ,
        …
        ,
        M
        ,
        +
        ∞
        }
      
    
    {\displaystyle \{1,\ldots ,M,+\infty \}}
  
 also exist. The best known algorithm for the directed case is in time 
  
    
      
        
          
            
              O
              ~
            
          
        
        (
        
          M
          
            1
            
              /
            
            (
            4
            −
            ω
            )
          
        
        
          V
          
            2
            +
            1
            
              /
            
            (
            4
            −
            ω
            )
          
        
        )
      
    
    {\displaystyle {\tilde {O}}(M^{1/(4-\omega )}V^{2+1/(4-\omega )})}
  
 by Zwick in 1998.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> 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 
  
    
      
        
          
            
              O
              ~
            
          
        
        (
        M
        
          V
          
            ω
          
        
        )
      
    
    {\displaystyle {\tilde {O}}(MV^{\omega })}
  
 by Shoshan and Zwick in 1999.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> The original implementation of this algorithm was erroneous and has been corrected by Eirinakis, Williamson, and Subramani in 2016.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Seidel, R. (1995). "On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs". Journal of Computer and System Sciences. 51 (3): 400–403. doi:10.1006/jcss.1995.1078. <a href="https://doi.org/10.1006%2Fjcss.1995.1078" target="_blank">https://doi.org/10.1006%2Fjcss.1995.1078</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Zwick, U. (1 November 1998). "All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms". Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). pp. 310–319. doi:10.1109/SFCS.1998.743464. ISBN 0-8186-9172-7. S2CID 10096418 – via IEEE Xplore. <a href="0-8186-9172-7" target="_blank">0-8186-9172-7</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Shoshan, A.; Zwick, U. (15 February 1999). "All pairs shortest paths in undirected graphs with integer weights". 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). pp. 605–614. doi:10.1109/SFFCS.1999.814635. ISBN 0-7695-0409-4. S2CID 2377466 – via IEEE Xplore. <a href="0-7695-0409-4" target="_blank">0-7695-0409-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Eirinakis, Pavlos; Williamson, Matthew; Subramani, K. (28 March 2016). "On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem". arXiv:1603.08627 [cs.DS]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Seidel's algorithm open-in-new

Seidel's algorithm