bellmann ford, gcd, lcm, ectended euclid

2 files changed, 23 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}