blob: d3d60947dc828f4b8f636841eb309953bdb199b7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// 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]) {
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]) {
// Negativer Kreis gefunden.
}}}
|
