\section{Leichteste Kreise}
\begin{tasks}
	\item
		Wir wenden Dijkstra auf den Graphen $G$ mit Startknoten $s$ an (\autoref{fig:edsger}).
		Das geht in $\Oh(n \log n)$ da Dijkstra in $\Oh(E + V \log V)$ läuft und die Kanten $m$ im planaren Graphen mit $m \leq 3n-6$ beschränkt sind.

		Einen Kreis der $s$ enthält existiert, wenn es in einem Teilbaum von $s$ des
		Kürzeste-Wege-Baums eine Rückwärtskante zu $s$ gibt.

		Haben wir eine Rückwärtskante in einem Teilbaum gefunden, lesen wir den kürzesten
		Weg von $s$ zu dem Knoten $a$ von dem die Rückwärtskante ausgeht, aus dem
		Kürzeste-Wege-Baum ab. Das Gewicht des Kreises erhalten wir, durch $a_d + \abs{as}$, wobei $a_d$ die Länge des kürzesten $s-a$-Weges ist und $\abs{as}$ das Kantengewicht der Kante $as$.

		Es reicht, die erste Rückwärtskante die wir finden zu nehmen.

		Das müssen wir nun für alle Teilbäume machen.
		Da der durchschnittliche Knotengrad im Graphen 
			


\end{tasks}

\begin{figure}
	\centering
	\includegraphics{edsger.png}
	\caption{Let's go Edsger! Shortest Path!}
	\label{fig:edsger}
\end{figure}