Floyd's Algorithmus für das All-pairs-shortest-path-Problem

Auch genannt ,,Kleene's Algorithmus``. Dieser Algorithmus ist ein weiteres Beispiel für dynamische Programmierung.

Sei G=(V,E) mit Distanzfunktion d:$A\rightarrow \mathbbm{R}_0^+$ gegeben. Sei o.B.d.A. $V=\{v_1, \ldots, v_n\}$.
Sei c_ij^k:= Länge eines kürzesten Pfades von v_i nach v_j, der als innerer Knoten (alle bis auf ersten und letzten Knoten) nur Knoten aus $\{v_i,\cdots,v_k\}$ enthält.

algorithm floyd:=

$\ulcorner$co $\forall i: d_{ii}=0$ od
for alle (i,j) do cij(0):= dij od  ; $1\leq i,j\leq n$for k:=1 to n do
		 for alle (i,j), $1\leq i,j\leq n$ do
		 		 $c_{ij}^{(k)} := \min\left\{c_{ij}^{(k-1)},\ c_{ik}^{(k-1)}+c_{kj}^{(k-1)}\right\}$		 od
od
$\llcorner$

Korrektheit:
Zu zeigen: c_ij^(k) des Algorithmus = c_ij^k (damit sind für k=n die Kosten der kürzesten Pfade durch c_ij^(k) gegeben).

Beweis: Richtig für k=0. Induktionsschluß: Ein kürzester Pfad von v_i nach v_j mit inneren Knoten $\in \{v_1,\ldots,v_{k+1}\}$ enthält entweder v_k+1 gar nicht als inneren Knoten, oder er enthält v_k+1 genau einmal als inneren Knoten. Im ersten Fall wurde dieser Pfad also bereits für c_ij^(k) betrachtet, hat also Länge $\geq c_{ij}^{(k)}$. Im zweiten Fall setzt er sich aus einem kürzesten Pfad P₁ von v_i nach v_k+1 und einem kürzesten Pfad von P₂ von v_k+1 nach v_j zusammen, wobei alle inneren Knoten von P₁ und P₂ $\in \{v_1,\ldots,v_k\}$ sind. Also ist die Länge des Pfades =c_i,k+1^(k)+c_k+1,j^(k). $\Diamond$