Seidel's algorithm

<p>Seidel's algorithm is an algorithm designed by <a href="/facts/Raimund_Seidel/u4XMgNom">Raimund Seidel</a> in 1992 for the <a href="/facts/Shortest_path_problem/g4nsrswr">all-pairs-shortest-path problem</a> for undirected, unweighted, connected graphs. It solves the problem in 
  
    
      
        O
        (
        
          V
          
            ω
          
        
        log
        ⁡
        V
        )
      
    
    {\displaystyle O(V^{\omega }\log V)}
  
 expected time for a graph with 
  
    
      
        V
      
    
    {\displaystyle V}
  
 vertices, where 
  
    
      
        ω
        <
        2.373
      
    
    {\displaystyle \omega <2.373}
  
 is the exponent in the complexity 
  
    
      
        O
        (
        
          n
          
            ω
          
        
        )
      
    
    {\displaystyle O(n^{\omega })}
  
 of 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 <a href="/facts/Computational_complexity_of_matrix_multiplication/KCn5KUzd">matrix multiplication</a>. 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 <a href="/facts/Connected_component_(graph_theory)/5owVSXtY">connected component</a> 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 
  
    
      
        ω
        =
        2
      
    
    {\displaystyle \omega =2}
  
 the expected running time becomes 
  
    
      
        O
        (
        
          V
          
            2
          
        
        
          log
          
            2
          
        
        ⁡
        V
        )
      
    
    {\displaystyle O(V^{2}\log ^{2}V)}
  
.
</p>

Seidel's algorithm open-in-new

Seidel's algorithm