Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Bäume Aufwärts: Hauptseite Algorithmen Vorherige Seite: Graphen - Tiefensuche/Breitensuche   Inhalt

Dijkstra-Beweis

Hinweis: Beim Daijkstra können wir gut eine Priorityqueue verwenden, um die Menge der noch nicht fixierten Knoten zu verwalten.

Startknoten ist der Knoten $v$. Wir haben eine Menge $D$, in welcher die Knoten enthalten sind, für die der kürzeste Weg von $v$ aus schon bestimmt ist2

Von einem Knoten $w$ dessen Abstand von $v$ $d(v,w)$ ist, können wir einen Knoten $x$, welcher noch nicht in der Menge $D$ enthalten ist, mit den minimalsten Kosten von $v$ erreichen. Wir wählen diesen Knoten. Formalisiert gilt für alle Paare $w'\in D\backslash w$ und $x'\in(V\backslash D)\backslash x$

\begin{displaymath}d(w,x)\leq d(w',x')\end{displaymath}

Würden wir nun einen Knoten $y\in V$ wählen, so würde gelten

\begin{displaymath}d(v,w)+d(w,x)\leq d(v,y)+d(y,x)\end{displaymath}

Wenn $y\in D$ ist $d(v,y)+d(y,x)$ größer als $d(v,x)$, da $d(v,x)$ schon am kleinsten ist, weil in der Menge $D$ schon alle kürzesten Pfade bestimmt sind.
Es ist unmöglich, daß $y\notin D$, da so der Weg $d(v,y)+d(y,x)$ garantiert größer ist, da über einen anderen Knoten aus $D$ gegangen werden muß und $d(v,x)$ minimal ist.

Fußnoten

... ist2
Diese Menge können wir nach und nach herstellen. Wir starten dabei mit der leeren Menge, weil der Knoten $v$ selbst mit der Weglänge $0$ erreichbar ist und dies garantiert auch der kürzeste Weg ist.
next up previous contents
Nächste Seite: Bäume Aufwärts: Hauptseite Algorithmen Vorherige Seite: Graphen - Tiefensuche/Breitensuche   Inhalt