From 8ceb0e35278563a3b315f04fc60fc9086d6c7a8a Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Fri, 14 Nov 2014 15:29:22 +0100 Subject: bellmann ford, gcd, lcm, ectended euclid --- graph/bellmannFord.cpp | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) create mode 100644 graph/bellmannFord.cpp (limited to 'graph/bellmannFord.cpp') 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 + } +} -- cgit v1.2.3