Die Idee dieses Algorithmusses ist es, daß für jeden Weg zu einem Knoten geprüft wird, ob er kürzer ist, wenn man direkt geht oder wenn man schon durch eine vorberechnete Menge D geht. Wird in der Menge D ein Knoten eingefügt, so wird versucht für jeden Knoten zu jedem Knoten einen Weg zu finden, der über diesen Knoten kürzer ist.

$\begin{displaymath}\Delta^{i+1}(v,w)=min\{\Delta^{i}(v,w),\Delta^{i}(v,v_{i+1})+\Delta^{i}(v_{i+1},w)\}\end{displaymath}$

Beispiel

$D_{0}=\emptyset$ :

	$v_{1}$	$v_{2}$	$v_{3}$	$v_{4}$	$v_{5}$
$v_{1}$	0	3	8	$\infty$	-4
$v_{2}$	$\infty$	0	$\infty$	1	7
$v_{3}$	$\infty$	4	0	$\infty$	$\infty$
$v_{4}$	2	$\infty$	-5	0	$\infty$
$v_{5}$	$\infty$	$\infty$	$\infty$	6	0

$D_{1}=\{v_{1}\}$ :

	$v_{1}$	$v_{2}$	$v_{3}$	$v_{4}$	$v_{5}$
$v_{1}$	0	3	8	$\infty$	-4
$v_{2}$	$\infty$	0	$\infty$	1	7
$v_{3}$	$\infty$	4	0	$\infty$	$\infty$
$v_{4}$	2	5	-5	0	-2
$v_{5}$	$\infty$	$\infty$	$\infty$	6	0

$D_{2}=\{v_{1},v_{2}\}$ :

	$v_{1}$	$v_{2}$	$v_{3}$	$v_{4}$	$v_{5}$
$v_{1}$	0	3	8	4	-4
$v_{2}$	$\infty$	0	$\infty$	1	7
$v_{3}$	$\infty$	4	0	5	11
$v_{4}$	2	5	-5	0	-2
$v_{5}$	$\infty$	$\infty$	$\infty$	6	0

$D_{3}=\{v_{1},v_{2},v_{3}\}$ :

	$v_{1}$	$v_{2}$	$v_{3}$	$v_{4}$	$v_{5}$
$v_{1}$	0	3	8	4	-4
$v_{2}$	$\infty$	0	$\infty$	1	7
$v_{3}$	$\infty$	4	0	5	11
$v_{4}$	2	-1	-5	0	-2
$v_{5}$	$\infty$	$\infty$	$\infty$	6	0

$D_{4}=\{v_{1},v_{2},v_{3},v_{4}\}$ :

	$v_{1}$	$v_{2}$	$v_{3}$	$v_{4}$	$v_{5}$
$v_{1}$	0	3	-1	4	-4
$v_{2}$	3	0	-4	1	-1
$v_{3}$	7	4	0	5	3
$v_{4}$	2	-1	-5	0	-2
$v_{5}$	8	5	1	6	0

$D_{5}=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}$ :

	$v_{1}$	$v_{2}$	$v_{3}$	$v_{4}$	$v_{5}$
$v_{1}$	0	1	-3	2	-4
$v_{2}$	3	0	-4	1	-1
$v_{3}$	7	4	0	5	3
$v_{4}$	2	-1	-5	0	-2
$v_{5}$	8	5	1	6	0

Negative Zyklen

Im Graphen dürfen keine negativen Zyklen vorkommen. Dann werden Pfade gebildet, die unendlich klein sind und das schafft dieser Algorithmus auch nicht.

Konstruktion des Pfades

Es reicht, wenn wir uns bei jeder Veränderung merken, über welchen Knoten wir die Kosten der Kante verändert haben. Dann können wir den Pfad rekursiv zurückverfolgen.

Warshall

Beim Warshall geht es nur um die Erreichbarkeitsanalyse. Wir verzichten deshalb auf Kantenkosten und legen nur eine Wahrheitstabelle an, die aussagt, ob ein Knoten von einem anderen aus erreichbar ist. Wir verwenden ein ähnliches Schema wie das des Floydalgorithmusses. Wir nehmen immer einen Knoten aus der noch nicht in D enthaltenen Menge mit hinzu und bestimmen für diesen für alle

Knoten:

$\begin{displaymath}R^{k+1}(i,j)=R^{k}(i,j)\wedge(R^{k}(i,j)\vee R^{k}(k,j)\end{displaymath}$

TSP

Das TSP (Traveling Salesman Problem - Problem eines Handlungsreisenden) ist das Problem den kürzesten Weg auf den Kanten durch alle Knoten zu finden, wobei jeder Knoten genau einmal besucht werden muß und auch demzufolge jede Kante nur einmal besucht werden darf. Das TSP-Problem ist das Problem einen Hamiltonkreis auf dem Graphen zu finden.
Auch das TSP läßt sich mit Hilfe des dynamischen Programmierens effinzienter lösen. Das naive Verfahren hat die Laufzeit

, da alle Permutationen ausprobiert werden müssen.

TSP mit dynamischen Programmieren

Die Laufzeit des TSP-Algorithmus läßt sich verringern, wenn man dynamisches Programmieren anwenden. Hierbei werden angefangen von allen zweielementigen Teilmengen die kürzesten Wege in allen Teilmengen gesucht, die dann letztendlich zu immer größeren Hamiltonwegen zusammengesetzt werden, bis letztendlich nur noch ein Hamiltonweg übrigbleibt³. Das ganze läuft in einer Laufzeit von $O(n^{2}\cdot 2^{n})$ mit einem Platz von $O(n\cdot 2^{n})$ .

Kosten TSP mit dynamischen Programmieren

Initialisieren kostet $\Theta(n)$ für jeden Knoten.
Kosten pro -elementige Teilmenge, die berechnet wird sind $\Theta(N_{W})$

$\begin{displaymath}N_{W}=\sum_{v\in W}\sum_{w\in(W\backslash\{v\})}1=l\cdot(l-1)\end{displaymath}$
Kosten summiert für alle Teilmengen von $v\backslash\{s\}$

$\begin{displaymath} \sum^{n}_{l=2}\sum_{w,wobei\,\,\vert w\vert=l}N_{W}=\end{displaymath}$

$\begin{displaymath}\begin {array}{ccc}\sum^{n}_{l=2}&\underbrace{n\choose l}&\underbrace{l\cdot(l-1)}\\ &=2^{n}&\leq n^{2}\\ \end {array}\end{displaymath}$

$\begin{displaymath}\Rightarrow\Theta(2^{n}n^{2})=\Theta(n^{2}2n)\end{displaymath}$
Platzkomplexität ist

$\begin{displaymath}Theta(n\cdot 2^{n}),\end{displaymath}$

da für jede Teilmenge die Kosten des kürzesten Weg4es und der kürzeste Weg gespeichert werden müssen.