bellmann ford, gcd, lcm, ectended euclid

6 files changed, 45 insertions, 0 deletions

diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp
new file mode 100644
index 0000000..94fa034
--- /dev/null
+++ b/graph/bellmannFord.cpp
@@ -0,0 +1,18 @@
+//n = number of vertices, edges is vector of edges
+dist.assign(n, INF); dist[0] = 0;
+parent.assign(n, -1);
+for (i = 0; i < n - 1; i++) {
+	for (j = 0; j < (int)edges.size(); j++) {
+		if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) {
+			dist[edges[j].to] = dist[edges[j].from] + edges[j].cost;
+			parent[edges[j].to] = edges[j].from;
+		}
+	}
+}
+//now dist and parent are correct shortest paths
+//next lines check for negative cycles
+for (j = 0; j < (int)edges.size(); j++) {
+	if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) {
+		//NEGATIVE CYCLE found
+	}
+}
diff --git a/graph/graph.tex b/graph/graph.tex
index 53cfb2a..4646ee3 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,5 +1,10 @@
 \section{Graphen}
 
+\subsection{Kürzeste Wege}
+
+\subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
+\lstinputlisting{graph/bellmannFord.cpp}
+
 \subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
 \lstinputlisting{graph/scc.cpp}
 
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp
new file mode 100644
index 0000000..6d9490f
--- /dev/null
+++ b/math/extendedEuclid.cpp
@@ -0,0 +1,11 @@
+//Accepted in Aufgabe mit Forderung: |X|+|Y| minimal (primaer) und X<=Y (sekundaer)
+//hab aber keinen Beweis dafuer :)
+ll x, y, d; //a * x + b * y = d = ggT(a,b)
+void extendedEuclid(ll a, ll b) {
+	if (!b) {
+		x = 1; y = 0; d = a; return;
+	}
+	extendedEuclid(b, a % b);
+	ll x1 = y; ll y1 = x - (a / b) * y;
+	x = x1; y = y1;
+}
\ No newline at end of file
diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp
new file mode 100644
index 0000000..3a0f742
--- /dev/null
+++ b/math/gcd-lcm.cpp
@@ -0,0 +1,7 @@
+ll gcd(ll a, ll b) {
+	return b == 0 ? a : gcd (b, a % b);
+}
+
+ll lcm(ll a, ll b) {
+	return a * (b / gcd(a, b)); //Klammern gegen Overflow
+}
\ No newline at end of file
diff --git a/math/math.tex b/math/math.tex
index e1e0950..0b66163 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,4 +1,8 @@
 \section{Mathe}
 
+\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
+\lstinputlisting{math/gcd-lcm.cpp}
+\lstinputlisting{math/extendedEuclid.cpp}
+
 \subsection{Binomialkoeffizienten}
 \lstinputlisting{math/binomial.cpp}
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index 5116dbf..c3429fb 100644
--- a/tcr.pdf
+++ b/tcr.pdf