Repository navigation
Expand file tree
/
Copy pathBellmanFord.java
More file actions
executable file
·61 lines (46 loc) · 1.71 KB
/
Copy pathBellmanFord.java
File metadata and controls
executable file
·61 lines (46 loc) · 1.71 KB
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
package BellmanFordAlgorithm;
import java.util.List;
public class BellmanFord {
private List<Vertex> vertexList;
private List<Edge> edgeList;
public BellmanFord(List<Vertex> vertexList, List<Edge> edgeList) {
this.vertexList = vertexList;
this.edgeList = edgeList;
}
public void bellmanFord(Vertex sourceVertex, Vertex targetVertex) {
sourceVertex.setMinDistance(0);
for (Vertex vertex : vertexList) {
for (Edge edge : edgeList) {
if ( edge.getStartVertex().getMinDistance() == Integer.MAX_VALUE ) {
continue;
}
int newDistance = edge.getStartVertex().getMinDistance() + edge.getWeight();
if (newDistance < edge.getTargetVertex().getMinDistance()) {
edge.getTargetVertex().setMinDistance(newDistance);
edge.getTargetVertex().setPreviousVertex(edge.getStartVertex());
}
}
}
for (Edge edge : edgeList) {
if (edge.getStartVertex().getMinDistance() != Integer.MAX_VALUE) {
if ( hasCycle(edge) ) {
System.out.println("Negative edge weight cycles detected!");
return;
}
}
}
if (targetVertex.getMinDistance() != Integer.MAX_VALUE) {
System.out.println("There is a shortest path from sourco to target, with cost: " + targetVertex.getMinDistance());
Vertex actualVErtex = targetVertex;
while( actualVErtex.getPreviousVertex() != null ){
System.out.print(actualVErtex+"-");
actualVErtex=actualVErtex.getPreviousVertex();
}
} else {
System.out.println("There is no path from source to target...");
}
}
private boolean hasCycle(Edge edge){
return edge.getTargetVertex().getMinDistance() > edge.getStartVertex().getMinDistance() + edge.getWeight();
}
}