-
-
Notifications
You must be signed in to change notification settings - Fork 609
/
BellmanFord.java
71 lines (63 loc) · 2.12 KB
/
BellmanFord.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
package algo.graph;
import ds.graph.Edge;
import ds.graph.WeightedGraph;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* Created by sherxon on 1/7/17.
*/
/**
* This Bellman Ford shortest path algorithm. It works with negative edges and if there negative cycle
* the algorithm reports. Time complexity is O(V*E) if E is V^2 , we can say that O(V^3).
* This is slower than Dijkstra shortest path algorithm which works for only non-negative edges in O(VLogV)
* with Fibonacci heap.
* */
public class BellmanFord {
WeightedGraph graph;
Map<Integer, Double> distance;
public BellmanFord(WeightedGraph graph) {
this.graph = graph;
distance = new HashMap<>();
}
public void shortestPath(Integer source) {
/**
* Step 1:
* Initialization step
* */
for (Integer vertex : graph.getVertices()) {
if (source.equals(vertex)) distance.put(vertex, 0d);
else distance.put(vertex, Double.POSITIVE_INFINITY);
}
/**
* Step 2:
*Relax all edges |V|-1 times. shortest path from source to any vertex can be found in |V|-1 iteration.
*
* */
List<Edge> edges=new LinkedList<>();
for (Integer vertex : graph.getVertices())
edges.addAll(graph.getEdges(vertex));
for (int i = 0; i < graph.size()-1; i++) {
for (Edge edge : edges) {
Double newPath = distance.get(edge.getFrom()) + edge.getWeight();
if (distance.get(edge.getTo()) > newPath) {
distance.put(edge.getTo(), newPath);
}
}
}
/**
* Step 3 :
* check negative cycle
* the above guarantees shortest path, if there another shortest path found that means
* there is a negative cycle
* */
for (Edge edge : edges) {
Double newPath = distance.get(edge.getFrom()) + edge.getWeight();
if (distance.get(edge.getTo()) > newPath) {
System.out.println("Negative Cycle found");
break;
}
}
}
}