Skip to content

Commit 56558d2

Browse files
giaunvgiaunv
committed
Shortest Path
1 parent 7835bdf commit 56558d2

5 files changed

Lines changed: 43 additions & 42 deletions

File tree

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/ShortestPathByBFS.java‎

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -9,13 +9,12 @@ public class ShortestPathByBFS {
99
public static Object[] shortestPathByBFS(GraphDirectedByAdjacencyList g, int source) {
1010
int[] distances = new int[g.getV()];
1111
int[] predecessors = new int[g.getV()];
12-
distances[source] = 0;
12+
1313
for (int v = 0; v < g.getV(); v++) {
14-
if (v != source) {
15-
distances[v] = INFINITE;
16-
predecessors[v] = UNDEFINED;
17-
}
14+
distances[v] = INFINITE;
15+
predecessors[v] = UNDEFINED;
1816
}
17+
distances[source] = 0;
1918

2019
boolean[] visited = new boolean[g.getV()];
2120
visited[source] = true;
@@ -53,7 +52,7 @@ static void printResult(Object[] paths) {
5352
Deque<Integer> route = new ArrayDeque<>();
5453
route.push(v);
5554
int u = predecessorsOfSource[v];
56-
while (u > 0) {
55+
while (u >= 0) {
5756
route.push(u);
5857
u = predecessorsOfSource[u];
5958
}

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/ShortestPathByBellmanFord.java‎

Lines changed: 21 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -10,13 +10,11 @@ static Object[] shortestPathByBellmanFord(GraphWeightedByAdjacencyList g, int so
1010
int[] distances = new int[g.getV()];
1111
int[] predecessors = new int[g.getV()];
1212

13-
distances[source] = 0;
1413
for (int v = 0; v < g.getV(); v++) {
15-
if (v != source) {
16-
distances[v] = INFINITE;
17-
predecessors[v] = UNDEFINED;
18-
}
14+
distances[v] = INFINITE;
15+
predecessors[v] = UNDEFINED;
1916
}
17+
distances[source] = 0;
2018

2119
for (int i = 1; i < g.getV(); i++) {
2220
for (int v = 0; v < g.getV(); v++) {
@@ -36,7 +34,8 @@ static Object[] shortestPathByBellmanFord(GraphWeightedByAdjacencyList g, int so
3634
if (distances[v] == INFINITE) continue;
3735
int alt = distances[v] + w.weight;
3836
if (alt < distances[w.vertex]) {
39-
throw new RuntimeException("Graph contains a negative-weight cycle");
37+
System.out.println("The input graph contains a negative-weight cycle");
38+
return new Object[]{};
4039
}
4140
}
4241
}
@@ -45,6 +44,8 @@ static Object[] shortestPathByBellmanFord(GraphWeightedByAdjacencyList g, int so
4544
}
4645

4746
static void printResult(Object[] paths) {
47+
if (paths.length == 0) return;
48+
4849
int[] distances = (int[]) paths[0];
4950
int[] predecessors = (int[]) paths[1];
5051

@@ -58,7 +59,7 @@ static void printResult(Object[] paths) {
5859
Deque<Integer> route = new ArrayDeque<>();
5960
route.push(v);
6061
int u = predecessors[v];
61-
while (u > 0) {
62+
while (u >= 0) {
6263
route.push(u);
6364
u = predecessors[u];
6465
}
@@ -68,12 +69,18 @@ static void printResult(Object[] paths) {
6869
}
6970

7071
public static void main(String[] args) {
71-
GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
72-
g.addEdge(0, 1, 19);
73-
g.addEdge(2, 0, 15);
74-
g.addEdge(2, 1, 17);
75-
g.addEdge(3, 2, 12);
76-
printResult(shortestPathByBellmanFord(g, 3));
77-
printResult(shortestPathByBellmanFord(g, 2));
72+
GraphWeightedByAdjacencyList g1 = new GraphWeightedByAdjacencyList(4);
73+
g1.addEdge(0, 1, -2);
74+
g1.addEdge(2, 0, 1);
75+
g1.addEdge(2, 1, 3);
76+
g1.addEdge(3, 2, 4);
77+
printResult(shortestPathByBellmanFord(g1, 3));
78+
79+
GraphWeightedByAdjacencyList g2 = new GraphWeightedByAdjacencyList(4);
80+
g2.addEdge(0, 1, -5);
81+
g2.addEdge(2, 0, 1);
82+
g2.addEdge(1, 2, 3);
83+
g2.addEdge(3, 2, 4);
84+
printResult(shortestPathByBellmanFord(g2, 3));
7885
}
7986
}

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/ShortestPathByDijkstra.java‎

Lines changed: 8 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -27,14 +27,12 @@ static Object[] shortestPathByDijkstra(GraphWeightedByAdjacencyList g, int sourc
2727
int[] predecessors = new int[g.getV()];
2828
Queue<Integer> queue = new ArrayDeque<>();
2929

30-
distances[source] = 0;
3130
for (int v = 0; v < g.getV(); v++) {
32-
if (v != source) {
33-
distances[v] = INFINITE;
34-
predecessors[v] = UNDEFINED;
35-
}
31+
distances[v] = INFINITE;
32+
predecessors[v] = UNDEFINED;
3633
queue.offer(v);
3734
}
35+
distances[source] = 0;
3836

3937
while (!queue.isEmpty()) {
4038
int v = minVertex(queue, distances);
@@ -69,7 +67,7 @@ static void printResult(Object[] paths) {
6967
Deque<Integer> route = new ArrayDeque<>();
7068
route.push(v);
7169
int u = predecessors[v];
72-
while (u > 0) {
70+
while (u >= 0) {
7371
route.push(u);
7472
u = predecessors[u];
7573
}
@@ -80,10 +78,10 @@ static void printResult(Object[] paths) {
8078

8179
public static void main(String[] args) {
8280
GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
83-
g.addEdge(0, 1, 19);
84-
g.addEdge(2, 0, 15);
85-
g.addEdge(2, 1, 17);
86-
g.addEdge(3, 2, 12);
81+
g.addEdge(0, 1, 2);
82+
g.addEdge(2, 0, 1);
83+
g.addEdge(2, 1, 5);
84+
g.addEdge(3, 2, 4);
8785
printResult(shortestPathByDijkstra(g, 3));
8886
printResult(shortestPathByDijkstra(g, 2));
8987
}

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/ShortestPathByDijkstraWithMinHeap.java‎

Lines changed: 8 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -13,15 +13,12 @@ static Object[] shortestPathByDijkstra(GraphWeightedByAdjacencyList g, int sourc
1313
int[] predecessors = new int[g.getV()];
1414
PriorityQueue<WeightedVertex> minHeap = new PriorityQueue<>(g.getV(), Comparator.comparingInt(WeightedVertex::getWeight));
1515

16-
distances[source] = 0;
1716
for (int v = 0; v < g.getV(); v++) {
18-
if (v != source) {
19-
distances[v] = INFINITE;
20-
predecessors[v] = UNDEFINED;
21-
}
22-
17+
distances[v] = INFINITE;
18+
predecessors[v] = UNDEFINED;
2319
minHeap.add(new WeightedVertex(v, distances[v]));
2420
}
21+
distances[source] = 0;
2522

2623
while (!minHeap.isEmpty()) {
2724
WeightedVertex v = minHeap.poll();
@@ -54,7 +51,7 @@ static void printResult(Object[] paths) {
5451
Deque<Integer> route = new ArrayDeque<>();
5552
route.push(v);
5653
int u = predecessors[v];
57-
while (u > 0) {
54+
while (u >= 0) {
5855
route.push(u);
5956
u = predecessors[u];
6057
}
@@ -65,10 +62,10 @@ static void printResult(Object[] paths) {
6562

6663
public static void main(String[] args) {
6764
GraphWeightedByAdjacencyList g = new GraphWeightedByAdjacencyList(4);
68-
g.addEdge(0, 1, 19);
69-
g.addEdge(2, 0, 15);
70-
g.addEdge(2, 1, 17);
71-
g.addEdge(3, 2, 12);
65+
g.addEdge(0, 1, 2);
66+
g.addEdge(2, 0, 1);
67+
g.addEdge(2, 1, 5);
68+
g.addEdge(3, 2, 4);
7269
printResult(shortestPathByDijkstra(g, 3));
7370
printResult(shortestPathByDijkstra(g, 2));
7471
}

‎datastructure-algorithm-java-examples/src/main/java/com/hellokoding/datastructure/graph/ShortestPathByFloydWarshall.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -17,7 +17,7 @@ public static int[][] shortestPathByBFSFloydWarshall(int[][] g) {
1717
}
1818

1919
if (distances[i][i] < 0) {
20-
System.out.println("Graph contains a negative-weight cycle");
20+
System.out.println("The input graph contains a negative-weight cycle");
2121
return new int[][]{};
2222
}
2323
}

0 commit comments

Comments
 (0)