From 53e7f12d828bb94c05d2b6c4e04d61de9482c426 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Thu, 3 Dec 2015 01:12:26 +0100
Subject: Improving graoh chapter.

---
 graph/bellmannFord.cpp | 40 ++++++++++++++++++++++++++--------------
 1 file changed, 26 insertions(+), 14 deletions(-)

(limited to 'graph/bellmannFord.cpp')

diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp
index 94fa034..45efd6b 100644
--- a/graph/bellmannFord.cpp
+++ b/graph/bellmannFord.cpp
@@ -1,18 +1,30 @@
-//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;
+// Laufzeit: O(|V|*|E|)
+struct edge {
+	int from; int to; int cost;
+	edge () {};
+	edge (int from, int to, int cost) : from(from), to(to), cost(cost) {};
+};
+
+vector<edge> edges; // Kanten einfügen!
+vector<int> dist, parent;
+
+void bellmannFord() {
+	dist.assign(NUM_VERTICES, INF); dist[0] = 0;
+	parent.assign(NUM_VERTICES, -1);
+	for (int i = 0; i < NUM_VERTICES - 1; i++) {
+		for (int 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
+
+	// "dist" und "parent" sind korrekte kürzeste Pfade.
+	// Folgende Zeilen prüfen nur negative Kreise.
+	for (int j = 0; j < (int)edges.size(); j++) {
+		if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) {
+			// Negativer Kreis gefunden.
+		}
 	}
 }
-- 
cgit v1.2.3