From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

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

(limited to 'graph/bellmannFord.cpp')

diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp
index d3d6094..21c7dbe 100644
--- a/graph/bellmannFord.cpp
+++ b/graph/bellmannFord.cpp
@@ -1,20 +1,19 @@
-// Laufzeit: O(|V|*|E|)
-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 (auto &e : edges) {
-			if (dist[e.from] + e.cost < dist[e.to]) {
+void bellmannFord(int n, vector<edge> edges, int start) {
+	vector<ll> dist(n, INF), parent(n, -1);
+	dist[start] = 0;
+	
+	for (int i = 1; i < n; i++) {
+		for (edge& e : edges) {
+			if (dist[e.from] != INF && 
+					dist[e.from] + e.cost < dist[e.to]) {
 				dist[e.to] = dist[e.from] + e.cost;
 				parent[e.to] = e.from;
 	}}}
 
-	// "dist" und "parent" sind korrekte kürzeste Pfade.
-	// Folgende Zeilen prüfen nur negative Kreise.
-	for (auto &e : edges) {
-		if (dist[e.from] + e.cost < dist[e.to]) {
+	for (edge& e : edges) {
+		if (dist[e.from] != INF &&
+				dist[e.from] + e.cost < dist[e.to]) {
 			// Negativer Kreis gefunden.
-}}}
+	}}
+	//return dist, parent;
+}
-- 
cgit v1.2.3