import java.util.*;
public class SPFA {
// The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman Ford algorithm which
// computes single-source shortest paths in a weighted directed graph.
final static int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
List<Edge> edges = new ArrayList<>();
/*
Graph with no negative weight cycles
>(1)
/ | \
2/ | \3
/ | \
(0) |5 > (2)
\ | /
8\ | / 3
\ v /
>(3)<
|
|
>(4)
|
|
>(5)
*/
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();
/*
Graph with no negative weight cycles
>(1)
/ A \
2/ | \3
/ | \
(0) |-8 > (2)
\ | /
8\ | / 3
\ | /
>(3)<
|
|
>(4)
|
|
>(5)
*/
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));
search2(edges, 6, 0, 5);
System.out.println("------------------------------------------------------");
search2(edges, 7, 0, 6);
}
public static int search(List<Edge> edges, int n, int start, int end) {
// Method does not support negative weight cycle.
Map<Integer, String> path = new HashMap<>();
path.put(start, start + "");
Queue<Integer> queue = new LinkedList();
// Any vertex serves as intermediate vertex will be set visited.
List<Integer> visited = new LinkedList<>();
int[][] weights = new int[n][n];
// Initialized with largest integer which represents no direct path from vertex a to b.
for (int i = 0; i < n; i++) {
Arrays.fill(weights[i], INF);
weights[i][i] = 0;
}
int[] lowestWeightPath = new int[n];
for (int i = 0; i < n; i++) {
lowestWeightPath[i] = weights[start][i];
}
for (Edge edge : edges) {
weights[edge.start][edge.end] = edge.weight;
if (edge.start == start) {
path.put(edge.end, start + "-->" + edge.end);
}
}
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
int interVertex = queue.poll();
// if vertex interVertex served as intermediate vertex, set it visited because all the
// possible links through interVertex are traversed.
visited.add(interVertex);
// walk to i from start through intermediate vertex interVertex
for (int i = 0; i < n; i++) {
if (i == interVertex || weights[interVertex][i] == INF || visited.contains(i)) {
continue;
}
queue.add(i);
// path from start to interVertex exists, so no need to verify the weights whether it's INF
int tmp = lowestWeightPath[interVertex] + weights[interVertex][i];
if (lowestWeightPath[i] > tmp) {
lowestWeightPath[i] = tmp;
if (interVertex != start) {
path.put(i, path.get(interVertex) + "-->" + i);
}
}
}
}
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");
}
return lowestWeightPath[end];
}
public static int search2(List<Edge> edges, int n, int start, int end) {
// Method supports negative weight cycle.
Map<Integer, String> path = new HashMap<>();
path.put(start, start + "");
Queue<Integer> queue = new LinkedList();
// Any vertex serves as intermediate vertex will be set visited.
List<Integer> visited = new LinkedList<>();
int[][] weights = new int[n][n];
// Initialized with largest integer which represents no direct path from vertex a to b.
for (int i = 0; i < n; i++) {
Arrays.fill(weights[i], INF);
weights[i][i] = 0;
}
int[] lowestWeightPath = new int[n];
for (int i = 0; i < n; i++) {
lowestWeightPath[i] = weights[start][i];
}
for (Edge edge : edges) {
weights[edge.start][edge.end] = edge.weight;
if (edge.start == start) {
path.put(edge.end, start + "-->" + edge.end);
}
}
// if the given graph contains negative cycle, you cannot set the accessed vertex visited.
// take the given graph for example, the first time original point goes to vertex 1, weight
// is 2;, after walking through 2, 3, 1, it becomes 1; if we iterate more times, the weight
// of start vertex to 1 will decrease from 1 to 0, -1, -2. If we set visited, we can only
// take path 2,3,1 once. Then we can not examine the cycle.
// variable count used to keep count of the visited times of certain vertex, if visited too many
// times, the given graph must contain negative cycle.
int[] count = new int[n];
queue.add(start);
visited.add(start);
boolean containsNegativeWeightCycle = false;
while (!queue.isEmpty()) {
int interVertex = queue.poll();
// if vertex interVertex served as intermediate vertex, set it visited because all the
// possible links through interVertex are traversed.
// visited.add(interVertex);
// walk to i from start through intermediate vertex interVertex
for (int i = 0; i < n; i++) {
if (i == interVertex || weights[interVertex][i] == INF || visited.contains(i)) {
continue;
}
queue.add(i);
// path from start to interVertex exists, so no need to verify the weights whether it's INF
int tmp = lowestWeightPath[interVertex] + weights[interVertex][i];
if (lowestWeightPath[i] > tmp) {
// assume i=1, every time walk through the cycle 1->2->3->1, weight[0][1] will decrease.
count[i]++;
if (count[i] > n) {
queue.clear();
containsNegativeWeightCycle = true;
break;
}
lowestWeightPath[i] = tmp;
if (interVertex != start) {
path.put(i, path.get(interVertex) + "-->" + i);
}
}
}
}
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");
}
return lowestWeightPath[end];
}
static class Edge {
int start = 0;
int end = 0;
int weight = 0;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
}