Seidels algoritm

Seidels algoritm är en algoritm designad av Raimund Seidel 1992 för problemet med alla-par-kortaste vägen för oriktade, oviktade, sammankopplade grafer. Det löser problemet i $O(V^{\omega }\log V)$ förväntad tid för en graf med $V$ hörn, där $\omega <2.373$ är exponenten i komplexiteten $O(n^{\omega })$ för $n\ gånger n$ matrismultiplikation . Om endast avstånden mellan varje par av hörn eftersträvas kan samma tidsgräns uppnås i värsta fall. Även om algoritmen är designad för anslutna grafer, kan den appliceras individuellt på varje ansluten komponent i en graf med samma körtid totalt sett. Det finns ett undantag från den förväntade körtiden som anges ovan för att beräkna banorna: om $\omega =2$ blir den förväntade körtiden $O(V^{ 2}\log ^{2}V)$ .

Detaljer om genomförandet

Kärnan i algoritmen är en procedur som beräknar längden på de kortaste vägarna mellan valfritt par av hörn. Detta kan göras i $O(V^{\omega }\log V)$ tid i värsta fall. När längderna väl har beräknats kan banorna rekonstrueras med en Las Vegas-algoritm vars förväntade körtid är $O(V^{\omega }\log V)$ för ${ \displaystyle \omega >2}$ och $O(V^{2}\log ^{2}V)$ för $\omega =2$ .

Beräknar de kortaste vägarnas längder

Python-koden nedan antar att inmatningsgrafen ges som en $n\times n$$0$ - $1$ närliggande matris $A$ med nollor på diagonalen. Den definierar funktionen APD som returnerar en matris med poster $D_{i,j}}$$D_{i,j}$ så att är längden på den kortaste vägen hörn $i$ och $j$ . Matrisklassen som används kan vara valfri matrisklassimplementering som stöder multiplikations-, exponentierings- och indexeringsoperatorerna (till exempel numpy.matrix ).

   
    
                 
         
        
      
                    0  0    
       
       
      
              
      
                          
       
      def  apd  (  A  ,  n  :  int  ):  """Beräkna de kortaste vägarnas längder."""  if  all  (  A  [  i  ][  j  ]  för  i  i  intervallet  (  n  )  för  j  i  intervallet  (  n  )  om  i  ! =  j  ):  returnera  A  Z  =  A  **  2  B  =  matris  ([  [  1  om  i  !=  j  och  (  A  [  i  ][  j  ]  ==  1  eller  Z  [  i  ][  j  ]  >  )  annat  för  j  in  intervall  (  n  )]  för  i  i  intervall  (  n  )])  T  =  apd  (  B  ,  n  )  X  =  T  *  A  grad  =  [  summa  (  A  [  i  ][  j  ]  för  j  i  intervall  (  n  ))  för  i  in  område  (  n  )]  D  =  matris  ([  [  2  *  T  [  i  ][  j  ]  om  X  [  i  ][  j  ]  >=  T  [  i  ][  j  ]  *  grad  [  j  ]  annars  2  *  T  [  i  ][  j  ]  -  1  för  j  i  intervallet  (  n  )]  för  i  i  intervallet  (  n  )])  return  D 

Basfallet testar om ingångsmatrisen beskriver en komplett graf, i vilket fall alla kortaste vägar har längden $1$ .

Grafer med vikter från ändliga universum

Algoritmer för oriktade och riktade grafer med vikter från ett ändligt universum $\{1,\ldots ,M,+\infty \}$ finns också. Den mest kända algoritmen för det riktade fallet är i tiden ${\tilde {O}}(M^{1/( 4-\omega )}V^{2+1/(4-\omega )})$ av Zwick 1998. Denna algoritm använder rektangulär matrismultiplikation istället för kvadratmatrismultiplikation. Bättre övre gränser kan erhållas om man använder den bästa rektangulära matrismultiplikationsalgoritmen som finns tillgänglig istället för att uppnå rektangulär multiplikation via multipla kvadratmatrismultiplikationer. Den mest kända algoritmen för det oriktade fallet är i tiden ${\tilde {O}}(MV^{\omega })$ av Shoshan och Zwick 1999. Den ursprungliga implementeringen av denna algoritm var felaktig och har korrigerats av Eirinakis, Williamson och Subramani 2016.