blob: 45efd6bab144ae1a9dba96022598c526ac027ee7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// 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;
}
}
}
// "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.
}
}
}
|
