# Dijkstra's Shortest Path Algorithm


import java.util.Scanner;

public class DijkstraShortestPath {

private DirectedEdge[] edgeTo;   // edgeTo[v] gives last edge on shortest
// known path from v to source vertex

private double[] distTo;         // distTo[v] gives lenght of shortest
// known path from v to source vertex

private IndexMinPQ<Double> pq;   // recall, dequeue() in a priority
// queue removes the element with
// the highest priority. Here, that
// will be the smallest path length
// to the source vertex

private int source;

public DijkstraShortestPath(EdgeWeightedDigraph g, int s) {

this.source = s;

// create/construct necessary arrays and priority queues...
edgeTo = new DirectedEdge[g.numVertices()];
distTo = new double[g.numVertices()];
pq = new IndexMinPQ<Double>(g.numVertices());

for (int v = 0; v < g.numVertices(); v++) {  // set all vertex distances to infinity
distTo[v] = Double.POSITIVE_INFINITY;
}
distTo[s] = 0.0;  // re-initialize source distance to 0

pq.insert(s, 0.0);

printTraceHeaders(); // just for the trace... (not part of the algorithm)

while (! pq.isEmpty()) {
int v = pq.delMin();   // note, this reduces the size of the queue...
for (DirectedEdge e : g.adj(v)) {
relax(e);
printTraceArraysAndQueue();           // just for the trace...  (not part of the algorithm)
}
}
}

public void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;

// now update priority queue...
if (pq.contains(w))
pq.decreaseKey(w, distTo[w]);  // overwrite distance associated with w to distTo[w]
else
pq.insert(w, distTo[w]);       // add vertex w, setting its distance to distTo[w]
}
}

public int source() {
return this.source;
}

public Stack<DirectedEdge> pathTo(int v) {
Stack<DirectedEdge> edges = new Stack<DirectedEdge>();

int w = v;
while (w != this.source()) {
DirectedEdge edge = edgeTo[w];
edges.push(edge);
w = edge.from();
}
return edges;
}

String s = "";
for (int i = 0; i < distTo.length; i++) {
s += i + "\t";
}

s += "|";

for (int i = 0; i < distTo.length; i++) {
s += i + "\t";
}

s += "  Priority Queue";
System.out.println(s);

final int NUM_SPACES_PER_TAB = 5;
for (int i = 0; i < s.length() + 2*NUM_SPACES_PER_TAB*distTo.length + 14; i++) {
System.out.print("-");
}
System.out.println();
}

public void printTraceArraysAndQueue() {
for (int i = 0; i < distTo.length; i++) {
String dist = (distTo[i] != Double.POSITIVE_INFINITY) ? Double.toString(distTo[i]) : "\u221E";
System.out.print(dist + "\t");
}

System.out.print("|");

for (int i = 0; i < edgeTo.length; i++) {
System.out.print(edgeTo[i] + "\t");
}

System.out.print("   ");
for (int i : pq) {
System.out.print(i + " ");
}
System.out.println();
}

public static void main(String[] args) {

EdgeWeightedDigraph g = new EdgeWeightedDigraph(args[0]);

System.out.print("Start? [0-"+(g.numVertices()-1)+"]");
Scanner scanner = new Scanner(System.in);
int s = scanner.nextInt();
System.out.print("Destination Vertex? [0-"+(g.numVertices()-1)+"]");
int v = scanner.nextInt();
DijkstraShortestPath sp = new DijkstraShortestPath(g,s);

System.out.println("\nshortest path from " + s + " to " + v + ":");
Stack<DirectedEdge> path = sp.pathTo(v);
for (DirectedEdge e : path) {
System.out.println(e.from() + "->" + e.to() + "  " + e.weight());
}

System.out.println("path length (approx) = " + sp.distTo[v]);
}
}