diff options
| -rw-r--r-- | graph/LCA.cpp | 2 | ||||
| -rw-r--r-- | graph/floydWarshall.cpp | 8 | ||||
| -rw-r--r-- | graph/graph.tex | 4 | ||||
| -rw-r--r-- | tcr.pdf | bin | 315778 -> 225861 bytes |
4 files changed, 13 insertions, 1 deletions
diff --git a/graph/LCA.cpp b/graph/LCA.cpp index d252bac..b4e6bdd 100644 --- a/graph/LCA.cpp +++ b/graph/LCA.cpp @@ -1,4 +1,4 @@ -//RMQ muss hinzugefügt werden! +//RMQ muss hinzugefuegt werden! vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); vector<vector<int>> graph(MAX_N); diff --git a/graph/floydWarshall.cpp b/graph/floydWarshall.cpp new file mode 100644 index 0000000..ee56441 --- /dev/null +++ b/graph/floydWarshall.cpp @@ -0,0 +1,8 @@ +//initialize adjmat, adjmat[i][i] = 0, adjmat[i][j] = INF if no edge is between i and j +for (k = 0; k < MAX_V; k++) { + for (i = 0; i < MAX_V; i++) { + for (j = 0; j < MAX_V; j++) { + if (adjmat[i][k] + adjmat[k][j] < adjmat[i][j]) adjmat[i][j] = adjmat[i][k] + adjmat[k][j]; + } + } +}
\ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index b35adc4..e3fd262 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -13,6 +13,10 @@ Kürzeste Pfade in Graphen ohne negative Kanten. Kürzestes Pfade in Graphen mit negativen Kanten. Erkennt negative Zyklen. \lstinputlisting{graph/bellmannFord.cpp} +\subsubsection{\textsc{Floyd-Warshall}-Algorithmus} +Alle kürzesten Pfade im Graphen. +\lstinputlisting{graph/floydWarshall.cpp} + \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} \lstinputlisting{graph/scc.cpp} |