diff options
| -rw-r--r-- | graph/dijkstra.cpp | 20 | ||||
| -rw-r--r-- | graph/graph.tex | 5 | ||||
| -rw-r--r-- | math/math.tex | 12 | ||||
| -rw-r--r-- | tcr.pdf | bin | 140656 -> 170218 bytes | |||
| -rw-r--r-- | tcr.tex | 5 |
5 files changed, 42 insertions, 0 deletions
diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp new file mode 100644 index 0000000..e7ec0c3 --- /dev/null +++ b/graph/dijkstra.cpp @@ -0,0 +1,20 @@ +priority_queue<ii, vector<ii>, greater<ii> > pq; +vector<int> dist; +dist.assign(NUM_VERTICES, INF); +dist[0] = 0; +pq.push(ii(0, 0)); + +while (!pq.empty()) { + di front = pq.top(); pq.pop(); + int curNode = front.second, curDist = front.first; + + if (curDist > dist[curNode]) continue; + + for (i = 0; i < (int)adjlist[curNode].size(); i++) { + int nextNode = adjlist[curNode][i].first, nextDist = curDist + adjlist[curNode][i].second; + + if (nextDist < dist[nextNode]) { + dist[nextNode] = nextDist; pq.push(ii(nextDist, nextNode)); + } + } +}
\ No newline at end of file diff --git a/graph/graph.tex b/graph/graph.tex index 4646ee3..2bf395c 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -2,7 +2,12 @@ \subsection{Kürzeste Wege} +\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. \lstinputlisting{graph/bellmannFord.cpp} \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)} diff --git a/math/math.tex b/math/math.tex index 0b66163..f82ab65 100644 --- a/math/math.tex +++ b/math/math.tex @@ -4,5 +4,17 @@ \lstinputlisting{math/gcd-lcm.cpp} \lstinputlisting{math/extendedEuclid.cpp} +\subsubsection{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$} +Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. +\begin{description} + \item[Falls $d = 1$:] ~ + \begin{itemize}[nosep] + \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit $\alpha x + \beta n = 1$ + \item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$ + \item $x^{-1} :\equiv \alpha \mod n$ + \end{itemize} + \item[Falls $d \neq 1$:] es existiert kein $x^{-1}$ +\end{description} + \subsection{Binomialkoeffizienten} \lstinputlisting{math/binomial.cpp}
\ No newline at end of file Binary files differ@@ -4,6 +4,11 @@ \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} +\usepackage{amsmath} +\usepackage{amssymb} + +\usepackage{enumitem} + \usepackage{color} \definecolor{darkred}{rgb}{0.72,0.07,0.07} \definecolor{darkgreen}{rgb}{0.23,0.62,0.22} |