Ein besserer Algorithmus für das All-pairs-shortest-distance-Problem
Ein besserer Algorithmus für das All-pairs-shortest-distance (bzw. paths)-Problem in ungewichteten Digraphen

$\!\!\!\!\left. \begin{array} {l} (d_{ij})_{0\leq i,j < n} \text{ Distanzmatri... ...ansitive H\uml {u}lle} \end{array} \right\}\text{alle Kantenl\uml {a}ngen = 1}$

$D^{(l)}=(d_{ij}^{(l)})_{o\leq i,j < n} \text{ mit }d_{ij}^{(l)}= \left\{ \beg... ... \text{ falls } d_{ij}^{*} \leq l \\ \infty \text{ sonst} \end{array} \right.$


algorithm 1 =

$\ulcorner$ 
co Sei $A=(a_{ij})_{0\leq i,j < n}$ mit $a_{ij}=\left\{
 \begin{array}
{l}
 1 \text{\ falls\ } d_{ij} \leq 1 \\  0 \text{\ sonst}
 \end{array}\right.$ oc 
co Sei B die Boolsche Einheitsmatrix oc 
for l:=2 to r+1 do
		 $B := A \cdot B;$ 
		 for $0 \leq i,j < n$ do
		 		 if bij=1 then dij(l):=l else $d_{ij}^{(l)}:=\infty$ fi;
		 		 if $d_{ij}^{(l-1)}\leq l$ then dij(l):=dij(l-1) fi
		 od 
od 
$\llcorner$

Dieser Algorithmus berechnet $D^{(1)}=D,D^{(2)},D^{(3)},\ldots,D^{(r)}$.
Sei $\omega$ eine Zahl $\geq 2$, so daß die Matrixmultiplikation in der Zeit $\mathcal{O}(n^\omega)$ durchgeführt werden kann (Winograd/Coppersmith: $\omega \leq 2,376$).

Zeitaufwand für Algorithmus 1:

algorithm apsd =

$\ulcorner$ 
Berechne, mit Algorithmus 1, $D^{(l)} \text{ f\uml {u}r } l=1,\ldots,r$;   
l:=r; 
for s:=1 to $\left\lceil\log_{\frac{3}{2}}{\frac{n}{r}}\right\rceil$ do
		 for i:=0 to n-1 do
		 		finde in der i-ten Zeile von D(l) den Wert d,     $\left\lceil\frac{l}{2}\right\rceil \leq d \leq l$, so daß d in der
		 		i-ten Zeile am wenigsten oft vorkommt;
		 		Si:= Menge der Spaltenindizes, in denen dieses d in der i-ten Zeile von
		 		D(l) vorkommt;
		 od
		 $l_1 := \left\lceil\frac{3}{2}l\right\rceil$;		 for $0 \leq i,j < n$ do
		 		 if $S_i \neq \emptyset$ then $m_{ij}:=
\underset 
<24517\gt\gt k\in S_i{{\min}\{d_{ik}^{(l)}+d_{kj}^{(l)}\}$ else $m_{ij}:=\infty$ fi;
		 		 if $d_{ij}^{(l)} \leq l$ then dij(l1):=dij(l)
		 		 elseif $m_{ij} \leq l_1$ then dij(l1)=mij
		 		 else $d_{ij}^{(l_1)}:=\infty$		 		 fi
		 od
		 l := l1; 
od
$\llcorner$

apsd berechnet:
Zunächst $D^{(1)}, \ldots, D^{(r)}$, dann D^(l) für

$$l=r, \left\lceil\frac{3}{2}r\right\rceil, \left\lceil\frac{... ...{3}{2}r\right\rceil\right\rceil,\ldots,\underbrace{n'}_{\geq n}$$

Da für d $\frac{l}{2}$ Werte zur Auswahl stehen, gilt:

$$\vert S_i\vert \leq \frac {2n}{l}$$

Damit ist die Laufzeit:

$$\mathcal{O}\left(rn^\omega + \sum_{s=1}^{\left\lceil\log_{\f... ...t r}\right) = \mathcal{O}\left(rn^\omega + \frac{n^3}{r}\right)$$

Setze r so, daß die beiden Summanden gleich sind, also $r=n^{\frac{3-\omega}{2}}$, dann ergibt sich damit für apsd die Laufzeit $\mathcal{O}\left(n^{\frac{3+\omega}{2}}\right)$.



Beweis: $\surd$ $\Diamond$



Bemerkung: apsp: Problem: Ausgabegröße kann $\Omega(n^3)$ sein:

Kürzeste Pfade-Nachfolger-Matrix $N \in [0,\ldots,n-1]^{n\times n}$
n_ij= Nummer des zweiten Knoten auf ,,dem`` kürzesten Pfad von Knoten i zu Knoten j. So eine Matrixdarstellung für die kürzesten Pfade zwischen allen Knotenpaaren kann in Zeit $\mathcal{O}(n^{\frac{3+\omega}{2}} \cdot \log^c n)$ für ein c > 0 bestimmt werden.




Idee: Ersetze

durch: