diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/floydWarshall.cpp | 12 | ||||
| -rw-r--r-- | graph/graph.tex | 10 |
2 files changed, 13 insertions, 9 deletions
diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp index 30d463a..6b303bb 100644 --- a/graph/floydWarshall.cpp +++ b/graph/floydWarshall.cpp @@ -1,10 +1,12 @@ // Laufzeit: O(|V|^3) -// Initialize adjmat: adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j, length otherwise. +// Initialisiere mat: mat[i][i] = 0, mat[i][j] = INF falls i & j nicht adjazent, Länge sonst. void floydWarshall() { - for (k = 0; k < NUM_VERTICES; k++) { - for (i = 0; i < NUM_VERTICES; i++) { - for (j = 0; j < NUM_VERTICES; j++) { - if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j]; + for (k = 0; k < MAX_V; k++) { + for (i = 0; i < MAX_V; i++) { + for (j = 0; j < MAX_V; j++) { + if (mat[i][k] != INF && mat[k][j] != INF && mat[i][k] + mat[k][j] < mat[i][j]) { + mat[i][j] = mat[i][k] + mat[k][j]; + } } } } diff --git a/graph/graph.tex b/graph/graph.tex index 8ac82e5..0661ae1 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -30,10 +30,12 @@ Erkennt negative Zyklen. \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} \lstinputlisting{graph/floydWarshall.cpp} \begin{itemize} - \item \textsc{Floyd-Warshall} findet auch negative Kreise. - Es existiert genau dann ein negativer Kreis, wenn \lstinline{dist[i][i] < 0} ist. - \item \textbf{Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen.} - Das ist fast immer ungewollt! + \item Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen. + Nur negative Werte sollten die Nullen überschreiben. + \item Von parallelen Kanten sollte nur die günstigste gespeichert werden. + \item Knoten \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist. + \item Ein u-v-Pfad existiert nicht, wenn \lstinline{dist[u][v] == INF}. + \item Gibt es einen Knoten \lstinline{c}, sodass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz. \end{itemize} \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} |