Ψ Die Informatikseite

Menü
Informatik » Bachelor » Algorithmen der Informatik » Dijkstra-Beweis
Graphen - Tiefensuche/Breitensuche Algorithmen der Informatik Bäume

Dijkstra-Beweis

Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus. Er bestimmt den kürzesten Pfad innerhalb eines Graphens von einem Startknoten zu entweder einem seiner Knoten oder allen seiner Knoten. Eine Einschränkung dieses Algorithmusses ist, dass er auf Graphen mit negativen Kantengewichten nicht anwendbar ist.

Der Algorithmus ist beispielsweise auf Wikipedia nachzulesen.

Beweis der Korrektheit

Hinweis: Beim Dijkstra 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.
Graphen - Tiefensuche/Breitensuche Algorithmen der Informatik Bäume