Skip to content

Commit e4f6b02

Browse files
devstromodevstromo
committed
Freestyle | Bellman–Ford Shortest Paths | Java
1 parent 6c616be commit e4f6b02

2 files changed

Lines changed: 241 additions & 0 deletions

File tree

‎freestyle/src/main/java/com/devstromo/graphs/bellman_ford/BellmanFord.java‎

Lines changed: 162 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,162 @@
1+
package com.devstromo.graphs.bellman_ford;
2+
3+
import java.util.*;
4+
5+
/**
6+
* Bellman–Ford shortest paths for directed graphs that may have negative weights.
7+
* Detects reachable negative cycles.
8+
* <p>
9+
* Works with:
10+
* - negative edges (allowed)
11+
* - negative cycles (reported)
12+
* - unreachable nodes (distance = Long.MAX_VALUE)
13+
* <p>
14+
* Time: O(V * E)
15+
* Space: O(V + E)
16+
*/
17+
public class BellmanFord {
18+
19+
public static class Graph {
20+
private final int n;
21+
private final List<Edge> edges = new ArrayList<>();
22+
23+
public Graph(int n) {
24+
if (n <= 0) throw new IllegalArgumentException("Number of nodes must be positive");
25+
this.n = n;
26+
}
27+
28+
/**
29+
* Adds a directed edge u -> v with weight w (may be negative).
30+
*/
31+
public void addEdge(int u, int v, long w) {
32+
if (u < 0 || u >= n || v < 0 || v >= n) {
33+
throw new IllegalArgumentException("Invalid endpoint");
34+
}
35+
edges.add(new Edge(u, v, w));
36+
}
37+
38+
public int size() {
39+
return n;
40+
}
41+
42+
public List<Edge> edges() {
43+
return edges;
44+
}
45+
}
46+
47+
public record Edge(int u, int v, long w) {
48+
}
49+
50+
public static class Result {
51+
public final long[] dist; // shortest distance from src; Long.MAX_VALUE if unreachable
52+
public final int[] parent; // parent[v] on shortest path, or -1
53+
public final int src;
54+
public final boolean hasNegativeCycle; // true if some node reachable from src is affected by a negative cycle
55+
56+
Result(long[] dist, int[] parent, int src, boolean hasNegativeCycle) {
57+
this.dist = dist;
58+
this.parent = parent;
59+
this.src = src;
60+
this.hasNegativeCycle = hasNegativeCycle;
61+
}
62+
63+
/**
64+
* Reconstructs shortest path from src to target; empty if unreachable or if negative cycle affects target.
65+
*/
66+
public List<Integer> reconstructPath(int target) {
67+
if (target < 0 || target >= dist.length) throw new IllegalArgumentException("Invalid target");
68+
if (dist[target] == Long.MAX_VALUE || hasNegativeCycle) return List.of();
69+
LinkedList<Integer> path = new LinkedList<>();
70+
for (int v = target; v != -1; v = parent[v]) path.addFirst(v);
71+
// sanity: should start at src if reachable
72+
if (path.isEmpty() || path.getFirst() != src) return List.of();
73+
return path;
74+
}
75+
76+
/**
77+
* If a negative cycle is reachable from src, returns one example cycle as a list of nodes (u0,u1,...,u0).
78+
* Returns empty list if none detected.
79+
*/
80+
public List<Integer> extractNegativeCycle(Graph g) {
81+
if (!hasNegativeCycle) return List.of();
82+
83+
int n = dist.length;
84+
int x = -1;
85+
86+
// Find a vertex that can still be relaxed (affected by neg cycle)
87+
long[] d = Arrays.copyOf(dist, n);
88+
int[] p = Arrays.copyOf(parent, n);
89+
90+
for (Edge e : g.edges()) {
91+
if (d[e.u] != Long.MAX_VALUE && d[e.u] + e.w < d[e.v]) {
92+
d[e.v] = Long.MIN_VALUE; // mark
93+
p[e.v] = e.u;
94+
x = e.v;
95+
}
96+
}
97+
if (x == -1) return List.of(); // should not happen if flag is set
98+
99+
// Move x back n times to ensure it's inside the cycle
100+
for (int i = 0; i < n; i++) x = p[x] == -1 ? x : p[x];
101+
102+
// Collect the cycle
103+
List<Integer> cycle = new ArrayList<>();
104+
int cur = x;
105+
do {
106+
cycle.add(cur);
107+
cur = p[cur];
108+
} while (cur != -1 && cur != x);
109+
110+
if (cur == -1 || cycle.isEmpty()) return List.of();
111+
Collections.reverse(cycle);
112+
// make it (u0..u_k, u0)
113+
cycle.add(cycle.get(0));
114+
return cycle;
115+
}
116+
}
117+
118+
/**
119+
* Runs Bellman–Ford from source src.
120+
* - Returns distances/parents
121+
* - hasNegativeCycle=true if a reachable negative cycle exists
122+
*/
123+
public static Result shortestPaths(Graph g, int src) {
124+
if (g == null) throw new IllegalArgumentException("Graph is null");
125+
if (src < 0 || src >= g.size()) throw new IllegalArgumentException("Invalid source");
126+
127+
int n = g.size();
128+
long[] dist = new long[n];
129+
int[] parent = new int[n];
130+
Arrays.fill(dist, Long.MAX_VALUE);
131+
Arrays.fill(parent, -1);
132+
133+
dist[src] = 0;
134+
135+
// Relax edges up to (n-1) times
136+
for (int i = 0; i < n - 1; i++) {
137+
boolean changed = false;
138+
for (Edge e : g.edges()) {
139+
if (dist[e.u] == Long.MAX_VALUE) continue;
140+
long nd = dist[e.u] + e.w;
141+
if (nd < dist[e.v]) {
142+
dist[e.v] = nd;
143+
parent[e.v] = e.u;
144+
changed = true;
145+
}
146+
}
147+
if (!changed) break; // early stop
148+
}
149+
150+
// One more pass to detect reachable negative cycles
151+
boolean hasNegCycle = false;
152+
for (Edge e : g.edges()) {
153+
if (dist[e.u] == Long.MAX_VALUE) continue;
154+
if (dist[e.u] + e.w < dist[e.v]) {
155+
hasNegCycle = true;
156+
break;
157+
}
158+
}
159+
160+
return new Result(dist, parent, src, hasNegCycle);
161+
}
162+
}

‎freestyle/src/test/java/com/devstromo/graphs/bellman_ford/BellmanFordUnitTest.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package com.devstromo.graphs.bellman_ford;
2+
3+
import static org.junit.jupiter.api.Assertions.*;
4+
5+
import org.junit.jupiter.api.DisplayName;
6+
import org.junit.jupiter.api.Test;
7+
8+
import java.util.List;
9+
10+
11+
public class BellmanFordUnitTest {
12+
13+
@Test
14+
@DisplayName("Test shortest paths with negative edges but no negative cycle")
15+
void testShortestPathsNoNegativeCycle() {
16+
BellmanFord.Graph g = new BellmanFord.Graph(5);
17+
g.addEdge(0, 1, 6);
18+
g.addEdge(0, 2, 7);
19+
g.addEdge(1, 2, 8);
20+
g.addEdge(1, 3, 5);
21+
g.addEdge(1, 4, -4);
22+
g.addEdge(2, 3, -3);
23+
g.addEdge(2, 4, 9);
24+
g.addEdge(3, 1, -2);
25+
g.addEdge(4, 0, 2);
26+
g.addEdge(4, 3, 7);
27+
28+
BellmanFord.Result r = BellmanFord.shortestPaths(g, 0);
29+
30+
assertFalse(r.hasNegativeCycle);
31+
assertEquals(0, r.dist[0]);
32+
assertEquals(2, r.dist[1]); // 0->2->3->1 : 7 + (-3) + (-2) = 2
33+
assertEquals(7, r.dist[2]); // 0->2
34+
assertEquals(4, r.dist[3]); // 0->2->3 : 7 + (-3) = 4
35+
assertEquals(-2, r.dist[4]); // 0->2->3->1->4 : 7 + (-3) + (-2) + (-4) = -2
36+
37+
// Path example (one valid shortest path)
38+
List<Integer> pathTo4 = r.reconstructPath(4);
39+
assertEquals(0, pathTo4.get(0));
40+
assertEquals(4, pathTo4.get(pathTo4.size() - 1));
41+
}
42+
43+
@Test
44+
@DisplayName("Test unreachable node")
45+
void testUnreachableNode() {
46+
BellmanFord.Graph g = new BellmanFord.Graph(3);
47+
g.addEdge(0, 1, 5);
48+
// node 2 is disconnected
49+
BellmanFord.Result r = BellmanFord.shortestPaths(g, 0);
50+
51+
assertEquals(0, r.dist[0]);
52+
assertEquals(5, r.dist[1]);
53+
assertEquals(Long.MAX_VALUE, r.dist[2]);
54+
assertTrue(r.reconstructPath(2).isEmpty());
55+
}
56+
57+
@Test
58+
@DisplayName("Test detection of reachable negative cycle")
59+
void testNegativeCycleDetection() {
60+
BellmanFord.Graph g = new BellmanFord.Graph(3);
61+
g.addEdge(0, 1, 1);
62+
g.addEdge(1, 2, -1);
63+
g.addEdge(2, 1, -1); // cycle of total weight -2 reachable from 0
64+
65+
BellmanFord.Result r = BellmanFord.shortestPaths(g, 0);
66+
assertTrue(r.hasNegativeCycle);
67+
68+
// Optional: try to extract a cycle (may vary in node order)
69+
List<Integer> cyc = r.extractNegativeCycle(g);
70+
// If provided, should be non-empty and closed (u0...u0)
71+
if (!cyc.isEmpty()) {
72+
assertTrue(cyc.size() >= 2);
73+
assertEquals(cyc.get(0), cyc.get(cyc.size() - 1));
74+
}
75+
76+
// When a negative cycle is reachable, we typically avoid returning paths
77+
assertTrue(r.reconstructPath(2).isEmpty());
78+
}
79+
}

0 commit comments

Comments
 (0)