import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class BellmanFord {
final static int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 2));
edges.add(new Edge(0, 3, 8));
edges.add(new Edge(1, 2, 3));
edges.add(new Edge(1, 3, 5));
edges.add(new Edge(2, 3, 3));
edges.add(new Edge(3, 4, 3));
edges.add(new Edge(4, 5, 1));
search(edges, 6, 0, 5);
System.out.println("------------------------------------------------------");
search(edges, 7, 0, 6);
System.out.println("\n####################################################");
System.out.println("Graph contains negative weight cycle");
System.out.println("####################################################\n");
edges.clear();
edges.add(new Edge(0, 1, 2));
edges.add(new Edge(0, 3, 8));
edges.add(new Edge(1, 2, 3));
edges.add(new Edge(3, 1, -7));
edges.add(new Edge(2, 3, 3));
edges.add(new Edge(3, 4, 3));
edges.add(new Edge(4, 5, 1));
search(edges, 6, 0, 5);
System.out.println("------------------------------------------------------");
search(edges, 7, 0, 6);
}
public static void search(List<Edge> edges, int n, int start, int end) {
Map<Integer, String> path = new HashMap<>();
long[] lowestWeightPath = new long[n];
for (int i = 1; i < n; i++) {
lowestWeightPath[i] = Integer.MAX_VALUE;
}
for (Edge edge : edges) {
if (edge.start == start) {
path.put(edge.end, start + "-->" + edge.end);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < edges.size(); j++) {
Edge edge = edges.get(j);
if (lowestWeightPath[edge.end] > lowestWeightPath[edge.start] + edge.weight) {
lowestWeightPath[edge.end] = lowestWeightPath[edge.start] + edge.weight;
path.put(j, path.get(edge.start) + "-->" + j);
}
}
}
boolean containsNegativeWeightCycle = false;
for (int i = 0; i < edges.size(); i++) {
Edge edge = edges.get(i);
if (lowestWeightPath[edge.end] > lowestWeightPath[edge.start] + edge.weight) {
containsNegativeWeightCycle = true;
break;
}
}
if (containsNegativeWeightCycle) {
try {
throw new Exception("Graph contains negative weight cycle");
} catch (Exception e) {
e.printStackTrace();
}
} else if (lowestWeightPath[end] != INF) {
System.out.println("From " + start + " to " + end + ", the lowest weight path " + path.get(end) + ", total weight is " + lowestWeightPath[end]);
} else {
System.out.println("From " + start + " to " + end + ", no path exists");
}
}
static class Edge {
public int start;
public int end;
public int weight;
Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
}
References
- https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/