From 0e845c6f6d967058e282747f6245d4e94fd094c6 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Fri, 17 Nov 2017 21:48:03 +0100 Subject: Changing few lines in Tipps/Tricks section and shortenig shortest paths section. --- graph/graph.tex | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) (limited to 'graph/graph.tex') 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. -- cgit v1.2.3