Why this matters when you build with AI
Ask an AI tool for a shortest path with some negative edges and it often writes Dijkstra. Dijkstra gives a wrong answer there, and the wrong answer looks reasonable. Ask the same tool for negative cycle detection and you often get a loop that runs the relaxation n times and prints "cycle found". That check misses a self-loop on a one-vertex graph, because the loop runs zero times when n is 1. Some versions print a cycle without checking that it really has a negative total.
You catch these in a few minutes. Test the code on a graph with one vertex and a negative self-loop. Test a graph where the negative cycle is not reachable from the source. Check that any printed cycle has a negative sum of weights. The lesson gives you the method and the tests.
A prompt that states the requirements:
Write a C++17 function that runs Bellman-Ford from source s on a directed graph with
integer weights (possibly negative). Return the shortest distance to each vertex, mark
each vertex whose distance is minus infinity, and return one negative cycle that is
reachable from s, as a list of vertices. Handle n = 1 and a negative self-loop.
Say how many rounds you run and why.A good answer runs n rounds (not n - 1), marks minus infinity with a search from the vertices that still improve in round n, and walks the parent pointers back n steps before it walks the cycle. Check each of these in the code. Then run the test in section "Check them against each other".
Terms used
- A negative cycle is a cycle (a path that returns to its start) whose weights add up to less than 0. Going around it once makes the total smaller, and going around again makes it smaller still.
- A negative cycle is reachable from source s if s can get to some vertex on it.
- Minus infinity (written
-infin the output) is the distance to a vertex that can be made arbitrarily small. This happens when some walk from s goes through a reachable negative cycle and then reaches the vertex. - A relaxation round is one pass over all m edges, in a fixed order. In each round we relax every edge once.
- A parent pointer for vertex v is the edge that last improved v. Following parent pointers backwards from v gives the path that the current distance of v came from.
- The queue-based variant, often called SPFA (Shortest Path Faster Algorithm), keeps a queue of vertices whose distance just changed, and relaxes only their outgoing edges.
- A walk is a path that may repeat vertices. A walk from s to v is longer than a simple path when it goes around a cycle.
The idea: rounds of relaxation
Bellman-Ford (described by Richard Bellman in "On a routing problem", Quarterly of Applied Mathematics, volume 16, 1958, pages 87 to 90, and by L. R. Ford Jr. in "Network Flow Theory", RAND Corporation paper P-923, 1956) is the simplest correct method with negative weights. Its one loop: run rounds, and in each round relax every edge once.
Why does this work? A shortest path that has no negative cycle is a simple path, so it uses at most n - 1 edges. After round k, every vertex whose shortest path has at most k edges already has its correct distance. So after n - 1 rounds all correct distances are set, and a round with no change is enough to stop.
A trace on a small graph
The graph has 4 vertices and source 0. Edges in input order:
0 -> 1 (weight 4) 0 -> 2 (weight 5) 2 -> 1 (weight -2) 1 -> 3 (weight 3)Start: distances are 0, INF, INF, INF.
round 1, edge 0->1: 4 is less than INF, so dist[1] = 4
round 1, edge 0->2: 5, so dist[2] = 5
round 1, edge 2->1: 5 - 2 = 3 is less than 4, so dist[1] = 3
round 1, edge 1->3: 3 + 3 = 6, so dist[3] = 6
round 2: no edge improves, so the distances are finalThe edge 2 -> 1 improved vertex 1 in the same round, because edges are relaxed in the order they are given. The order changes how many rounds are needed, not the final answer. Real output of the program on this graph (file bf_trace.txt):
0 0
1 3
2 5
3 6
no negative cycleRound 2 has to run to see that nothing changes. That is why the main loop in the code runs up to n rounds, and why the last round is the test for a negative cycle.
Negative cycles
What a negative cycle does
Suppose the cycle 1 -> 2 -> 1 has weights -1 and -1, so its total is -2. Then the walk from s to 1, then around the cycle any number of times, then to any other vertex, gives a smaller and smaller total. The true distance is minus infinity, so no finite number is correct. Every vertex reachable from the cycle inherits this.
A negative cycle that s cannot reach does not matter. Its vertices keep finite distances, or stay unreachable.
Detection with round n
If there is no negative cycle reachable from s, rounds stop after at most n - 1 rounds, as shown above. So if round n still improves an edge, a negative cycle is reachable.
Why? Take a vertex that improves in round n. Its best walk from s has at least n edges, so it repeats a vertex somewhere. Removing a cycle from a walk never increases the total when the cycle is not negative. If all the cycles inside that walk were non-negative, we could remove them and get a simple path with a total no larger than the walk. But every simple path has a total at least as large as the distances after n - 1 rounds, and the walk is already smaller than that. So at least one cycle inside the walk is negative, and it is reachable from s.
Marking minus infinity
Every vertex that improves in round n is reachable from a negative cycle, by the argument above, so its distance is minus infinity. The vertices that are reachable from those are minus infinity too. The code marks all of them with one search from the round-n vertices.
Is that all of the minus-infinity vertices? Yes. Let C be any reachable negative cycle. Suppose no edge of C improves in round n. Then for every edge of C, the distance at its end is not more than the distance at its start plus the weight. Adding these inequalities around the cycle, the distances cancel, and we get that zero is not more than the total weight of C. That total is negative, which is a contradiction. So at least one edge of C improves in round n. So some vertex of C improves in round n, and everything reachable from C is found by the search.
Recovering a cycle from parent pointers
We want a list of vertices of a negative cycle, not just the fact that one exists. Each vertex stores pe[v], the index of the edge that last improved it. Following pe backwards from a vertex goes along its parent chain.
Start at a vertex x that improved in round n. Walk back n steps along parent pointers. The usual textbook argument is that after n steps you are standing on a cycle of the parent graph. From there, walk the cycle once and collect its vertices. Every cycle in the parent graph has a negative total (a standard lemma, stated in Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms", third edition, MIT Press, 2009). The stress test in this lesson checks that the printed cycle really is negative, on about 18000 random graphs.
The n steps matter. Section "Common mistakes" shows what the output looks like without them.
The C++17 code
Bellman-Ford takes O(n m) time. For n = 2000 and m = 10^5 that is about 2 * 10^8 relaxation steps, which is usually fine in C++. Python is too slow for limits like that, so this lesson shows only C++.
The header bellman.hpp holds everything. bellman_ford returns the distances, the minus-infinity marks and one cycle. spfa is the queue-based variant. It returns distances and one cycle, but it does not mark minus infinity. For that, use bellman_ford.
bellman.hpp:
// bellman.hpp: Bellman-Ford, queue-based Bellman-Ford (SPFA), negative cycles and -inf marks.
#pragma once
#include <algorithm>
#include <limits>
#include <queue>
#include <vector>
using ll = long long;
const ll INF = std::numeric_limits<ll>::max() / 4; // "unreachable" marker
struct Edge {
int from, to;
ll w;
};
struct Result {
std::vector<ll> dist; // shortest distance from src, INF if unreachable
std::vector<int> pe; // pe[v] = index in edges of the edge that last improved v, -1 if none
std::vector<char> neg_inf; // neg_inf[v] = 1 if the true distance to v is minus infinity
bool has_cycle = false; // a negative cycle is reachable from src
std::vector<int> cycle; // vertices of one such cycle: c0 -> c1 -> ... -> c0
};
// Start at x and walk back n parent steps. Then we stand on a cycle of the parent graph.
// Walk that cycle once and return its vertices in forward (edge) order.
// Returns an empty list if the parent chain ends early, which should not happen.
std::vector<int> recover_cycle(int n, const std::vector<Edge>& edges, const std::vector<int>& pe, int x) {
int y = x;
for (int i = 0; i < n; i++) {
if (pe[y] < 0) return {};
y = edges[pe[y]].from;
}
std::vector<int> back; // y, parent(y), parent(parent(y)), ... until we return to y
int z = y;
do {
if (pe[z] < 0 || (int)back.size() > n) return {};
back.push_back(z);
z = edges[pe[z]].from;
} while (z != y);
std::reverse(back.begin(), back.end()); // now each vertex has an edge to the next one
return back;
}
// Classic Bellman-Ford. Time O(n * m). Works with negative weights.
Result bellman_ford(int n, const std::vector<Edge>& edges, int src) {
Result r;
r.dist.assign(n, INF);
r.pe.assign(n, -1);
r.neg_inf.assign(n, 0);
r.dist[src] = 0;
std::vector<int> improved_last; // vertices improved in round n
for (int round = 1; round <= n; round++) {
improved_last.clear();
for (int i = 0; i < (int)edges.size(); i++) {
const Edge& e = edges[i];
if (r.dist[e.from] == INF) continue; // nothing to relax from an unreached vertex
ll nd = r.dist[e.from] + e.w;
if (nd < r.dist[e.to]) {
r.dist[e.to] = nd;
r.pe[e.to] = i;
improved_last.push_back(e.to);
}
}
if (improved_last.empty()) break; // a full round with no change: distances are final
}
if (improved_last.empty()) return r; // no negative cycle reachable from src
// Round n still improved something, so a negative cycle is reachable from src.
r.has_cycle = true;
r.cycle = recover_cycle(n, edges, r.pe, improved_last.back());
// Every vertex reachable from an improved vertex has distance minus infinity.
std::vector<std::vector<int>> out(n);
for (const Edge& e : edges) out[e.from].push_back(e.to);
std::vector<int> stack;
for (int v : improved_last)
if (!r.neg_inf[v]) {
r.neg_inf[v] = 1;
stack.push_back(v);
}
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
for (int v : out[u])
if (!r.neg_inf[v]) {
r.neg_inf[v] = 1;
stack.push_back(v);
}
}
return r;
}
// Queue-based Bellman-Ford (SPFA). Only a vertex whose distance changed goes into the queue again.
// It finds distances and one negative cycle. It does not mark -inf vertices; use bellman_ford for that.
// Stop rule: a vertex that is pushed n times means a negative cycle is reachable.
Result spfa(int n, const std::vector<Edge>& edges, int src) {
Result r;
r.dist.assign(n, INF);
r.pe.assign(n, -1);
r.neg_inf.assign(n, 0);
std::vector<std::vector<int>> out(n); // indices of the edges that leave each vertex
for (int i = 0; i < (int)edges.size(); i++) out[edges[i].from].push_back(i);
std::vector<char> in_queue(n, 0);
std::vector<int> pushes(n, 0);
std::queue<int> q;
r.dist[src] = 0;
q.push(src);
in_queue[src] = 1;
pushes[src] = 1;
int bad = -1;
while (!q.empty() && bad < 0) {
int u = q.front();
q.pop();
in_queue[u] = 0;
for (int i : out[u]) {
const Edge& e = edges[i];
ll nd = r.dist[u] + e.w;
if (nd < r.dist[e.to]) {
r.dist[e.to] = nd;
r.pe[e.to] = i;
if (!in_queue[e.to]) {
in_queue[e.to] = 1;
if (++pushes[e.to] >= n) {
bad = e.to;
break;
}
q.push(e.to);
}
}
}
}
if (bad >= 0) {
r.has_cycle = true;
r.cycle = recover_cycle(n, edges, r.pe, bad);
}
return r;
}The SPFA stop rule deserves a word. A vertex enters the queue again only when its distance drops while it is not already queued. If no negative cycle is reachable, a vertex cannot enter the queue n times. The tests below check both directions: no false alarms on graphs without a negative cycle, and an alarm on every graph with one.
bf_main.cpp reads a graph and prints the result. Mode bf or spfa:
// bf_main.cpp: reads "n m s", then m lines "u v w" (directed edges). Prints results from s.
// Usage: ./bf bf|spfa < input
#include <cstdio>
#include <string>
#include <vector>
#include "bellman.hpp"
int main(int argc, char** argv) {
int n, m, s;
if (scanf("%d %d %d", &n, &m, &s) != 3) return 1;
std::vector<Edge> edges;
for (int i = 0; i < m; i++) {
int u, v;
ll w;
if (scanf("%d %d %lld", &u, &v, &w) != 3) return 1;
edges.push_back({u, v, w});
}
std::string mode = argc > 1 ? argv[1] : "bf";
Result r = mode == "spfa" ? spfa(n, edges, s) : bellman_ford(n, edges, s);
for (int v = 0; v < n; v++) {
if (r.neg_inf[v])
printf("%d -inf\n", v);
else if (r.dist[v] >= INF)
printf("%d inf\n", v);
else
printf("%d %lld\n", v, r.dist[v]);
}
if (r.has_cycle) {
printf("negative cycle:");
for (size_t i = 0; i < r.cycle.size(); i++) printf("%s%d", i ? " -> " : " ", r.cycle[i]);
if (!r.cycle.empty()) printf(" -> %d", r.cycle[0]);
printf("\n");
} else {
printf("no negative cycle\n");
}
return 0;
}Compile and run:
g++ -O2 -std=c++17 -Wall -Wextra -o bf bf_main.cpp
./bf bf < bf_demo.txt
./bf spfa < bf_demo.txtWorked example with a negative cycle
The input file bf_demo.txt has 8 vertices and source 0:
8 10 0
0 1 4
0 2 5
1 2 -2
2 3 3
3 4 -1
4 2 -3
4 5 2
5 6 1
0 6 9
1 7 -1The cycle 2 -> 3 -> 4 -> 2 has weights 3, -1 and -3. Its total is -1, so it is negative. Vertices 2 to 6 are reachable from it, so their distances are minus infinity. Vertex 1 is reachable from 0 but not from the cycle, so it keeps distance 4. Vertex 7 is reached through vertex 1, so its distance is 4 - 1 = 3. Real output of ./bf bf:
0 0
1 4
2 -inf
3 -inf
4 -inf
5 -inf
6 -inf
7 3
negative cycle: 2 -> 3 -> 4 -> 2Real output of ./bf spfa on the same file:
0 0
1 4
2 -5
3 -1
4 -2
5 1
6 2
7 3
negative cycle: 4 -> 2 -> 3 -> 4The two outputs name the same cycle, but they start at different vertices. The queue variant also does not mark minus infinity, so the numbers -5, -1, -2, 1 and 2 are not distances. Do not use them. The variant reports that a cycle exists and gives one cycle, and that is all it promises.
Complexity
bellman_ford takes O(n m) time and O(n + m) memory. The minus-infinity search takes O(n + m) on top. spfa has the same O(n m) worst case, and on many inputs it does far fewer relaxations, because it only looks at vertices that changed. Do not rely on the speed of SPFA when a time limit is strict. The worst case is still O(n m).
Check them against each other
The stress test bf_stress.cpp builds random graphs with up to 7 vertices and weights from -5 to 9. For each graph it computes the truth in two independent ways:
- Negative cycles and minus-infinity marks come from Floyd-Warshall (from the previous lesson). A vertex y is on a negative closed walk when
D[y][y]is negative, and y must be reachable from the source. Everything reachable from such a y is minus infinity. - Distances for vertices that are not minus infinity come from n - 1 plain relaxation rounds. That is correct for those vertices, as argued above.
It then checks that bellman_ford and spfa agree on whether a cycle exists, that the minus-infinity marks match, and that the printed cycle is a real cycle: its vertices are distinct, each step is an edge, the cheapest edge at each step sums to a negative number, and the cycle is reachable from the source.
bf_stress.cpp:
// bf_stress.cpp: random graphs with negative weights. Checks bellman_ford and spfa
// against brute force: Floyd-Warshall reachability for negative cycles and -inf marks,
// and n - 1 plain relaxation rounds for distances of vertices that are not -inf.
// Usage: ./bf_stress [seed] [graphs]
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <random>
#include <vector>
#include "bellman.hpp"
struct Raw {
int u, v;
ll w;
};
std::vector<ll> brute_dist(int n, const std::vector<Raw>& es, int s) {
std::vector<ll> d(n, INF);
d[s] = 0;
for (int it = 0; it < n - 1; it++)
for (const Raw& e : es)
if (d[e.u] < INF && d[e.u] + e.w < d[e.v]) d[e.v] = d[e.u] + e.w;
return d;
}
int main(int argc, char** argv) {
unsigned seed = argc > 1 ? (unsigned)std::strtoul(argv[1], nullptr, 10) : 1;
int graphs = argc > 2 ? std::atoi(argv[2]) : 2000;
std::mt19937 rng(seed);
int with_cycle = 0;
for (int t = 0; t < graphs; t++) {
int n = 1 + (int)(rng() % 7);
int m = (int)(rng() % (3 * n + 1));
int s = (int)(rng() % n);
std::vector<Raw> es;
std::vector<Edge> edges;
for (int i = 0; i < m; i++) {
Raw e{(int)(rng() % n), (int)(rng() % n), (ll)(rng() % 15) - 5}; // weights -5..9
es.push_back(e);
edges.push_back({e.u, e.v, e.w});
}
// Brute force 1: Floyd-Warshall on all pairs (negative weights allowed).
std::vector<std::vector<ll>> D(n, std::vector<ll>(n, INF));
for (int i = 0; i < n; i++) D[i][i] = 0;
for (const Raw& e : es) D[e.u][e.v] = std::min(D[e.u][e.v], e.w);
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++) {
if (D[i][k] == INF) continue;
for (int j = 0; j < n; j++)
if (D[k][j] < INF) D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]);
}
// y is on a negative closed walk (so on a negative cycle) and y is reachable from s.
std::vector<char> cyc_reach(n, 0);
bool brute_cycle = false;
for (int y = 0; y < n; y++)
if (D[s][y] < INF && D[y][y] < 0) {
brute_cycle = true;
cyc_reach[y] = 1;
}
std::vector<char> brute_neg(n, 0);
for (int v = 0; v < n; v++)
for (int y = 0; y < n; y++)
if (cyc_reach[y] && D[y][v] < INF) brute_neg[v] = 1;
// Brute force 2: n - 1 rounds of relaxation, valid for vertices that are not -inf.
std::vector<ll> ref = brute_dist(n, es, s);
// Minimum weight of an edge u -> v, for checking recovered cycles.
std::vector<std::vector<ll>> W(n, std::vector<ll>(n, INF));
for (const Raw& e : es) W[e.u][e.v] = std::min(W[e.u][e.v], e.w);
Result bf = bellman_ford(n, edges, s);
Result sp = spfa(n, edges, s);
bool ok = bf.has_cycle == brute_cycle && sp.has_cycle == brute_cycle;
for (int v = 0; v < n && ok; v++) {
if (bf.neg_inf[v] != brute_neg[v]) ok = false;
if (!brute_neg[v] && bf.dist[v] != ref[v]) ok = false;
if (!brute_neg[v] && !brute_cycle && sp.dist[v] != ref[v]) ok = false;
}
if (ok && brute_cycle) {
with_cycle++;
for (const Result* r : {&bf, &sp}) {
const std::vector<int>& c = r->cycle;
if (c.empty() || D[s][c[0]] == INF) ok = false;
// Distinct vertices, every step is an edge, and the cheapest edges sum to a negative total.
ll total = 0;
for (size_t i = 0; i < c.size() && ok; i++) {
int a = c[i], b = c[(i + 1) % c.size()];
for (size_t j = i + 1; j < c.size(); j++)
if (c[j] == a) ok = false;
if (W[a][b] >= INF) ok = false;
else total += W[a][b];
}
if (ok && total >= 0) ok = false;
}
} else if (ok) {
if (!bf.cycle.empty() || !sp.cycle.empty()) ok = false;
}
if (!ok) {
printf("MISMATCH on graph %d (n=%d, m=%d, s=%d)\n", t, n, m, s);
return 1;
}
}
printf("all %d random graphs agree (%d with a reachable negative cycle)\n", graphs, with_cycle);
return 0;
}Real output:
g++ -O2 -std=c++17 -Wall -Wextra -o bf_stress bf_stress.cpp
./bf_stress 1 5000
./bf_stress 2024 5000
./bf_stress 77 8000all 5000 random graphs agree (1836 with a reachable negative cycle)
all 5000 random graphs agree (1893 with a reachable negative cycle)
all 8000 random graphs agree (3044 with a reachable negative cycle)The seeds fix the graphs, so the same seeds should print the same lines on your machine. These tests use at most 7 vertices. They do not show that the code is fast on large graphs.
Two of the cases the test caught are worth seeing. Both were produced on purpose by making a wrong copy of the header (in scratch folders, not in the lesson files). Their output is real:
round loop changed to n - 1 rounds: MISMATCH on graph 4 (n=1, m=3, s=0)
parent walk of n steps removed: MISMATCH on graph 1 (n=6, m=18, s=1)Common mistakes
Mistake 1: running n - 1 rounds, or running the test loop for the wrong count. With n = 1 the loop runs zero times, so a negative self-loop on the single vertex is never seen. The real symptom in the test is the mismatch line above, with n = 1. In a contest the symptom is "no negative cycle" for a graph that has one. Run the round loop n times, and check the one-vertex case by hand.
Mistake 2: printing the start vertex of the round-n change as the cycle. The vertex that improved in round n is not necessarily on the cycle. It may be downstream of it. You must walk back n parent steps first. The second mismatch line above shows what happens without the walk: the printed list is not a negative cycle. Symptom: a "cycle" whose edges do not exist or whose total is not negative.
Mistake 3: marking only the cycle vertices as minus infinity. Vertices reachable from the cycle also have minus infinity. If you only mark the cycle, a vertex downstream keeps a finite number, which is wrong. Use the search from all round-n vertices, as the code does.
Mistake 4: reporting a cycle that the source cannot reach. This is a correctness rule. A negative cycle that s cannot reach does not change any distance from s. Try the input below. The program must print "no negative cycle".
4 3 0
0 1 1
2 3 -1
3 2 -1Real output:
0 0
1 1
2 inf
3 inf
no negative cycleMistake 5: relaxing from an unreached vertex. If dist[u] is INF, then dist[u] + w is a huge number, or it overflows if INF is INT_MAX. The code skips unreached vertices, and so should yours. Symptom: an unreachable vertex appears with a finite or negative distance.
Mistake 6: treating SPFA's numbers as distances after a cycle. On a graph with a reachable negative cycle, the queue variant stops early, and the distances it left are not the true distances. The real output above shows -5, -1 and -2 for vertices that are in fact minus infinity. Only use spfa to learn that a cycle exists and to get one cycle.
Checklist
- Negative weights present? Use Bellman-Ford, not Dijkstra.
- Run n rounds. The last round is the cycle test.
- A vertex that improves in round n is downstream of a negative cycle. Mark it and everything reachable from it as minus infinity.
- To print a cycle, start at a round-n vertex, walk back n parent steps, then walk the cycle once.
- Check the printed cycle: distinct vertices, every step is an edge, the total is negative.
- Check reachability from the source before reporting a cycle.
- Test the one-vertex case and a negative self-loop.
- Use SPFA for speed on typical inputs only if you do not need the minus-infinity marks; its worst case is still O(n m).
What was checked
- All C++ code compiled with g++ 15.2.0 (Ubuntu) using
-O2 -std=c++17 -Wall -Wextra, with no warnings. bf_stresspassed on 5000 graphs with seed 1, 5000 with seed 2024, and 8000 with seed 77. The graphs have up to 7 vertices and weights from -5 to 9. Each run is against the Floyd-Warshall and relaxation brute force described above.- The two deliberate wrong variants (n - 1 rounds, no parent walk) each failed the stress test, as shown.
- The outputs in this lesson were copied from the program runs.
- I did not time the code on large graphs. The O(n m) figure is a bound, not a measurement.
- The citations were checked in search results. Bellman (1958) is "On a routing problem", Quarterly of Applied Mathematics, volume 16, pages 87 to 90. Ford (1956) is RAND paper P-923, "Network Flow Theory". Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms", third edition, MIT Press, 2009, was confirmed through bookseller listings. I did not read the full text of any of them.
Summary
Bellman-Ford handles negative weights by relaxing all edges in rounds. A change in round n means a negative cycle is reachable from the source. The vertices that change in that round, and everything they reach, have minus-infinity distance. A cycle is printed by walking back n parent steps and then around the loop. The queue-based variant finds a cycle faster on many inputs, but it does not mark minus infinity, so use the classic version when you need all the marks.
Practice
Problem 1: which vertices are minus infinity
Input (file bf_p1.txt):
5 6 0
0 1 2
1 2 -1
2 1 -1
3 4 -5
4 3 1
2 4 1Which vertices have distance minus infinity, and which has a finite distance? Name one negative cycle the program could report.
Show the answer
Hint: find every cycle, add its weights, and ask whether the source reaches it. Then follow the edges out of the cycle.
Answer: vertex 0 has distance 0. Vertices 1, 2, 3 and 4 are minus infinity. The cycle 1 -> 2 -> 1 has total -2 and is reachable from 0. The cycle 3 -> 4 -> 3 has total -4 and is reachable from 0 through the edge 2 -> 4. The program printed negative cycle: 3 -> 4 -> 3. Real output:
0 0
1 -inf
2 -inf
3 -inf
4 -inf
negative cycle: 3 -> 4 -> 3Problem 2: check a printed cycle
A program prints the cycle 5 -> 2 -> 7 -> 5 for a graph with 8 vertices. Describe the checks you run on it before you trust it, and say what each check catches.
Show the answer
Hint: the checks are about the vertices and about the weights, not about the algorithm.
Answer: first, the vertices must be distinct, since a cycle that repeats a vertex is a walk. Second, each consecutive pair must be an edge of the graph, including the last to the first. Third, add the weight of the cheapest edge for each consecutive pair, and the sum must be negative. Fourth, the first vertex must be reachable from the source. The first check catches a repeated vertex, the second catches a made-up step, the third catches a non-negative loop, and the fourth catches a cycle the source cannot reach. The stress test uses all four.
Problem 3: no cycle here
Input (file bf_p3.txt):
4 3 0
0 1 1
2 3 -1
3 2 -1The graph has a negative cycle 2 -> 3 -> 2. Does the program report it? Why or why not?
Show the answer
Hint: which vertices can source 0 reach?
Answer: no. Source 0 reaches only vertices 0 and 1, so the cycle 2 -> 3 -> 2 is not reachable from it. The program prints no negative cycle, with distances 0, 1, inf and inf. The cycle does not change any distance from source 0. Run from source 2 instead, and the answer changes.
Problem 4: same cycle, different output
The graph from the worked example is in bf_demo.txt. Bellman-Ford prints the cycle starting from vertex 2. The queue variant prints the same cycle starting from vertex 4. Are both answers correct? Explain.
Show the answer
Hint: what does a cycle as a list of vertices mean, and does its starting point matter?
Answer: both are correct. A cycle is the same cycle whatever vertex you start the listing from, as long as the edges go in the same direction. Both printed lists use the edges 2 -> 3, 3 -> 4 and 4 -> 2, so both describe the cycle with total -1.
Problem 5: count the minus-infinity vertices
In bf_demo.txt, how many vertices have distance minus infinity from source 0? Do not count vertex 1 or vertex 7.
Show the answer
Hint: a vertex is minus infinity if the cycle can reach it.
Answer: 5. They are vertices 2, 3, 4, 5 and 6. Vertex 1 keeps distance 4, and vertex 7 keeps distance 3, because the cycle cannot reach either of them.