-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
BellmanFordEdgeList.java
105 lines (90 loc) · 3.49 KB
/
BellmanFordEdgeList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
* An implementation of the Bellman-Ford algorithm. The algorithm finds the shortest path between a
* starting node and all other nodes in the graph. The algorithm also detects negative cycles.
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.graphtheory;
public class BellmanFordEdgeList {
// A directed edge
public static class Edge {
double cost;
int from, to;
public Edge(int from, int to, double cost) {
this.to = to;
this.from = from;
this.cost = cost;
}
}
/**
* An implementation of the Bellman-Ford algorithm. The algorithm finds the shortest path between
* a starting node and all other nodes in the graph. The algorithm also detects negative cycles.
* If a node is part of a negative cycle then the minimum cost for that node is set to
* Double.NEGATIVE_INFINITY.
*
* @param edges - An edge list containing directed edges forming the graph
* @param V - The number of vertices in the graph.
* @param start - The id of the starting node
*/
public static double[] bellmanFord(Edge[] edges, int V, int start) {
double[] dist = new double[V];
java.util.Arrays.fill(dist, Double.POSITIVE_INFINITY);
dist[start] = 0;
// Only in the worst case does it take V-1 iterations for the Bellman-Ford
// algorithm to complete. Another stopping condition is when we're unable to
// relax an edge, this means we have reached the optimal solution early.
boolean relaxedAnEdge = true;
// For each vertex, apply relaxation for all the edges
for (int v = 0; v < V - 1 && relaxedAnEdge; v++) {
relaxedAnEdge = false;
for (Edge edge : edges) {
if (dist[edge.from] + edge.cost < dist[edge.to]) {
dist[edge.to] = dist[edge.from] + edge.cost;
relaxedAnEdge = true;
}
}
}
// Run algorithm a second time to detect which nodes are part
// of a negative cycle. A negative cycle has occurred if we
// can find a better path beyond the optimal solution.
relaxedAnEdge = true;
for (int v = 0; v < V - 1 && relaxedAnEdge; v++) {
relaxedAnEdge = false;
for (Edge edge : edges) {
if (dist[edge.from] + edge.cost < dist[edge.to]) {
dist[edge.to] = Double.NEGATIVE_INFINITY;
relaxedAnEdge = true;
}
}
}
// Return the array containing the shortest distance to every node
return dist;
}
public static void main(String[] args) {
int E = 10, V = 9, start = 0;
Edge[] edges = new Edge[E];
edges[0] = new Edge(0, 1, 1);
edges[1] = new Edge(1, 2, 1);
edges[2] = new Edge(2, 4, 1);
edges[3] = new Edge(4, 3, -3);
edges[4] = new Edge(3, 2, 1);
edges[5] = new Edge(1, 5, 4);
edges[6] = new Edge(1, 6, 4);
edges[7] = new Edge(5, 6, 5);
edges[8] = new Edge(6, 7, 4);
edges[9] = new Edge(5, 7, 3);
double[] d = bellmanFord(edges, V, start);
for (int i = 0; i < V; i++)
System.out.printf("The cost to get from node %d to %d is %.2f\n", start, i, d[i]);
// Output:
// The cost to get from node 0 to 0 is 0.00
// The cost to get from node 0 to 1 is 1.00
// The cost to get from node 0 to 2 is -Infinity
// The cost to get from node 0 to 3 is -Infinity
// The cost to get from node 0 to 4 is -Infinity
// The cost to get from node 0 to 5 is 5.00
// The cost to get from node 0 to 6 is 5.00
// The cost to get from node 0 to 7 is 8.00
// The cost to get from node 0 to 8 is Infinity
}
}