import java.util.*;
public class Dijkstra {
// Dijkstra doesn't work for Graphs with negative weight cycles. Because Dijkstra only focus on the
// path from start vertex to others, but the negative weight cycles may not contain it.
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, -8));
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 int search(List<Edge> edges, int n, int start, int end) {
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;
}
for (Edge edge : edges) {
weights[edge.start][edge.end] = edge.weight;
}
// used to keep the visiting path
Map<Integer, String> detailedPath = new HashMap<>();
// The path from start to x with smallest weight, where x means other points.
int[] smallestWeightPath = new int[n];
for (int i = 0; i < n; i++) {
smallestWeightPath[i] = weights[start][i];
detailedPath.put(i, start +"");
}
visited.add(start);
while (visited.size() < n) {
// Get the closest vertex to start point which is not visited yet. It will serve as
// the intermediate vertex through which start point can link to other vertexes.
int interVertex = getClosestUnvisited(visited, smallestWeightPath);
// Stop searching if no appropriate vertexes found.
if (interVertex == -1) {
break;
}
// if vertex interVertex served as intermediate vertex, set it visited because all the
// possible links through interVertex are traversed.
visited.add(interVertex);
for (int j = 0; j < n; j++) {
// the same vertex or not linked
if (interVertex == j || weights[interVertex][j] == INF) {
continue;
}
// move to j from start through intermediate vertex interVertex
int tmp = smallestWeightPath[interVertex] + weights[interVertex][j];
if (smallestWeightPath[j] > tmp) {
smallestWeightPath[j] = tmp;
detailedPath.put(j, detailedPath.get(interVertex) + "-->" + j);
}
}
}
if (smallestWeightPath[end] != INF) {
System.out.println("From " + start + " to " + end + ", the smallest weight path " + detailedPath.get(end) + ", total weight is " + smallestWeightPath[end]);
} else {
System.out.println("From " + start + " to " + end + ", no path exists");
}
return smallestWeightPath[end];
}
private static int getClosestUnvisited(List<Integer> visited, int[] shortestPath) {
int idx = -1;
int min = Integer.MAX_VALUE;
for (int i = 0; i < shortestPath.length; i++) {
if (visited.contains(i)) {
continue;
}
if (shortestPath[i] < min) {
min = shortestPath[i];
idx = i;
}
}
return idx;
}
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;
}
}
}