From 9d121e24674cc1355d27ff35688a205766333928 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 19:53:09 +0200 Subject: Bellmann Ford now with C++11. --- graph/bellmannFord.cpp | 26 ++++++++------------------ 1 file changed, 8 insertions(+), 18 deletions(-) (limited to 'graph/bellmannFord.cpp') diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp index 45efd6b..d3d6094 100644 --- a/graph/bellmannFord.cpp +++ b/graph/bellmannFord.cpp @@ -1,10 +1,4 @@ // 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 edges; // Kanten einfügen! vector dist, parent; @@ -12,19 +6,15 @@ 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; - } - } - } + for (auto &e : edges) { + if (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 (int j = 0; j < (int)edges.size(); j++) { - if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to]) { + for (auto &e : edges) { + if (dist[e.from] + e.cost < dist[e.to]) { // Negativer Kreis gefunden. - } - } -} +}}} -- cgit v1.2.3