Skip to content

Commit 6c616be

Browse files
devstromodevstromo
committed
Freestyle | Dijkstra's Shortest Path | Java
1 parent 95339f4 commit 6c616be

2 files changed

Lines changed: 186 additions & 0 deletions

File tree

‎freestyle/src/main/java/com/devstromo/graphs/dijkstra/Dijkstra.java‎

Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
package com.devstromo.graphs.dijkstra;
2+
3+
import java.util.*;
4+
5+
/**
6+
* Dijkstra's shortest path algorithm for directed graphs with non-negative weights.
7+
* Uses an adjacency list and a min-heap (PriorityQueue).
8+
* <p>
9+
* Time: O((V + E) log V)
10+
* Space: O(V + E)
11+
*/
12+
public class Dijkstra {
13+
14+
public static class Graph {
15+
private final int n;
16+
private final List<List<Edge>> adj;
17+
18+
public Graph(int n) {
19+
if (n <= 0) throw new IllegalArgumentException("Number of nodes must be positive");
20+
this.n = n;
21+
this.adj = new ArrayList<>(n);
22+
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
23+
}
24+
25+
/**
26+
* Adds a directed edge u -> v with non-negative weight w.
27+
*/
28+
public void addEdge(int u, int v, long w) {
29+
validateNode(u);
30+
validateNode(v);
31+
if (w < 0) throw new IllegalArgumentException("Dijkstra requires non-negative weights");
32+
adj.get(u).add(new Edge(v, w));
33+
}
34+
35+
private void validateNode(int u) {
36+
if (u < 0 || u >= n) throw new IllegalArgumentException("Invalid node: " + u);
37+
}
38+
39+
public int size() {
40+
return n;
41+
}
42+
43+
public List<List<Edge>> edges() {
44+
return adj;
45+
}
46+
}
47+
48+
public static class Edge {
49+
final int to;
50+
final long w;
51+
52+
Edge(int to, long w) {
53+
this.to = to;
54+
this.w = w;
55+
}
56+
}
57+
58+
public static class Result {
59+
public final long[] dist; // dist[i] = shortest distance from src to i, Long.MAX_VALUE if unreachable
60+
public final int[] parent; // parent[i] = previous node on shortest path from src to i, or -1 if none
61+
public final int src;
62+
63+
Result(long[] dist, int[] parent, int src) {
64+
this.dist = dist;
65+
this.parent = parent;
66+
this.src = src;
67+
}
68+
69+
/**
70+
* Reconstruct shortest path from the source to target as a list of nodes.
71+
* Returns empty list if target is unreachable.
72+
*/
73+
public List<Integer> reconstructPath(int target) {
74+
if (target < 0 || target >= dist.length) throw new IllegalArgumentException("Invalid target");
75+
if (dist[target] == Long.MAX_VALUE) return List.of();
76+
LinkedList<Integer> path = new LinkedList<>();
77+
for (int v = target; v != -1; v = parent[v]) path.addFirst(v);
78+
return path;
79+
}
80+
}
81+
82+
/**
83+
* Runs Dijkstra from a single source.
84+
*/
85+
public static Result shortestPaths(Graph g, int src) {
86+
if (g == null) throw new IllegalArgumentException("Graph is null");
87+
if (src < 0 || src >= g.size()) throw new IllegalArgumentException("Invalid source");
88+
89+
int n = g.size();
90+
long[] dist = new long[n];
91+
int[] parent = new int[n];
92+
Arrays.fill(dist, Long.MAX_VALUE);
93+
Arrays.fill(parent, -1);
94+
95+
dist[src] = 0;
96+
97+
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
98+
// each entry: [distance, node]
99+
pq.offer(new long[]{0, src});
100+
101+
boolean[] settled = new boolean[n];
102+
103+
while (!pq.isEmpty()) {
104+
long[] cur = pq.poll();
105+
long d = cur[0];
106+
int u = (int) cur[1];
107+
108+
if (settled[u]) continue; // lazy deletion
109+
settled[u] = true;
110+
111+
if (d > dist[u]) continue; // stale entry guard (extra safety)
112+
113+
for (Edge e : g.edges().get(u)) {
114+
int v = e.to;
115+
long nd = d + e.w;
116+
if (nd < dist[v]) {
117+
dist[v] = nd;
118+
parent[v] = u;
119+
pq.offer(new long[]{nd, v});
120+
}
121+
}
122+
}
123+
124+
return new Result(dist, parent, src);
125+
}
126+
}

‎freestyle/src/test/java/com/devstromo/graphs/dijkstra/DijkstraUnitTest.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package com.devstromo.graphs.dijkstra;
2+
3+
import org.junit.jupiter.api.DisplayName;
4+
import org.junit.jupiter.api.Test;
5+
6+
import java.util.List;
7+
8+
import static org.junit.jupiter.api.Assertions.*;
9+
10+
class DijkstraUnitTest {
11+
@Test
12+
@DisplayName("Test shortest distances on a small directed graph")
13+
void testShortestDistances() {
14+
Dijkstra.Graph g = new Dijkstra.Graph(6);
15+
g.addEdge(0, 1, 7);
16+
g.addEdge(0, 2, 9);
17+
g.addEdge(0, 5, 14);
18+
g.addEdge(1, 2, 10);
19+
g.addEdge(1, 3, 15);
20+
g.addEdge(2, 3, 11);
21+
g.addEdge(2, 5, 2);
22+
g.addEdge(3, 4, 6);
23+
g.addEdge(5, 4, 9);
24+
25+
Dijkstra.Result r = Dijkstra.shortestPaths(g, 0);
26+
27+
assertEquals(0, r.dist[0]);
28+
assertEquals(7, r.dist[1]);
29+
assertEquals(9, r.dist[2]);
30+
assertEquals(20, r.dist[3]);
31+
assertEquals(20, r.dist[4]);
32+
assertEquals(11, r.dist[5]);
33+
34+
// Path checks
35+
assertEquals(List.of(0, 2, 5), r.reconstructPath(5));
36+
assertEquals(List.of(0, 2, 5, 4), r.reconstructPath(4));
37+
}
38+
39+
@Test
40+
@DisplayName("Test unreachable node remains at infinity and path is empty")
41+
void testUnreachable() {
42+
Dijkstra.Graph g = new Dijkstra.Graph(4);
43+
g.addEdge(0, 1, 3);
44+
// Node 2 and 3 are disconnected from source 0
45+
Dijkstra.Result r = Dijkstra.shortestPaths(g, 0);
46+
47+
assertEquals(0, r.dist[0]);
48+
assertEquals(3, r.dist[1]);
49+
assertEquals(Long.MAX_VALUE, r.dist[2]);
50+
assertEquals(Long.MAX_VALUE, r.dist[3]);
51+
assertTrue(r.reconstructPath(2).isEmpty());
52+
}
53+
54+
@Test
55+
@DisplayName("Test negative weight rejection")
56+
void testNegativeWeight() {
57+
Dijkstra.Graph g = new Dijkstra.Graph(2);
58+
assertThrows(IllegalArgumentException.class, () -> g.addEdge(0, 1, -1));
59+
}
60+
}

0 commit comments

Comments
 (0)