\documentclass{bschlangaul-aufgabe}
\bLadePakete{syntax}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 7},
  Thematik = {Pseudo-Code Dijkstra},
  Referenz = 66115-2015-F.T2-A7,
  RelativerPfad = Examen/66115/2015/03/Thema-2/Aufgabe-7.tex,
  ZitatSchluessel = examen:66115:2015:03,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Dijkstra},
  EinzelpruefungsNr = 66115,
  Jahr = 2015,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 7,
}

Auf folgendem ungerichteten, gewichteten Graphen wurde der
Dijkstra-Algorithmus (wie auf der nächsten Seite beschrieben)
ausgeführt, doch wir wissen lediglich, welcher Knoten als letztes
schwarz (black) wurde (Nr. 8) und was seine Distanz zum Startknoten (Nr.
1) ist. Die Gewichte der Kanten sind angegeben.\index{Algorithmus von Dijkstra}
\footcite{examen:66115:2015:03}

Finden Sie zunächst den Startknoten, nummerieren Sie anschließend die
Knoten in der Reihenfolge, in der sie schwarz wurden, und geben Sie in
jedem Knoten die Distanz zum Startknoten an.

Hinweis: Der Startknoten ist eindeutig.

Dijkstra(WeightedGraph G, Vertex s)

\begin{minted}{md}
Initialize(G, s);
S=ß;
Q = new PriorityQueue(V, d) ;
while not Q.Empty() do
  u = Q.ExtractMin() ;
  S = S U {u};
  foreach v € Adj[u| do
    Relax(u, v; w);

  u.color = black;
\end{minted}

Initialize(Graph G, Vertex s)

\begin{minted}{md}
foreach u € V do
  u.color = white;
  u.d = 00;
s.color = gray;
s.d = 0;
\end{minted}

Relax(u, v; w)

\begin{minted}{md}
if v.d> u.d+ w(u,v) then
  v.color = gray;
  v.d = u.d + w(u,v);
  Q.DecreaseKey(v, v.d);
\end{minted}

\end{document}