diff options
Diffstat (limited to 'graph/graph.tex')
| -rw-r--r-- | graph/graph.tex | 17 |
1 files changed, 9 insertions, 8 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index f52ed59..6761e16 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,19 +13,20 @@ \subsection{Kürzeste Wege} -\subsubsection{Algorithmus von \textsc{Dijkstra}} -Kürzeste Pfade in Graphen ohne negative Kanten. +% \subsubsection{Algorithmus von \textsc{Dijkstra}} +% Kürzeste Pfade in Graphen ohne negative Kanten. \lstinputlisting{graph/dijkstra.cpp} -\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} -Kürzestes Pfade in Graphen mit negativen Kanten. -Erkennt negative Zyklen. +% \subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +% Kürzestes Pfade in Graphen mit negativen Kanten. +% Erkennt negative Zyklen. \lstinputlisting{graph/bellmannFord.cpp} -\subsubsection{\textsc{Floyd-Warshall}-Algorithmus} -\lstinputlisting{graph/floydWarshall.cpp} +% \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} +% \lstinputlisting{graph/floydWarshall.cpp} +Floyd Warshall: \begin{itemize}[nosep] - \item Nur negative Werte sollten die Nullen überschreiben. + \item Nur negative Werte sollten die Nullen bei Schlingen überschreiben. \item Von parallelen Kanten sollte nur die günstigste gespeichert werden. \item \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist. \item Wenn für \lstinline{c} gilt, dass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz. |