import java.util.Scanner;
import java.util.Stack;

public class DijkstraShortestPaths {

    private int source;
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private IndexMinPQ<Double> pq;
    
    public DijkstraShortestPaths(WeightedDigraph g, int source) {
        this.source = source;
        
        //construct necessary arrays, priority queues..
        edgeTo = new DirectedEdge[g.numVertices()];
        distTo = new double[g.numVertices()];
        pq = new IndexMinPQ<Double>(g.numVertices());
        
        //initialize distances to source..
        for (int v = 0; v < g.numVertices(); v++) {
            distTo[v] = Double.POSITIVE_INFINITY;
        }
        distTo[source] = 0.0;
        
        pq.insert(source,0.0);
        
        while (!pq.isEmpty()) {
            int v = pq.delMin();
            
            for (DirectedEdge e : g.adj(v)) {
                relax(e);
            }
        }
    }
    
    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;
            if (pq.contains(w)) {
                pq.decreaseKey(w, distTo[w]); 
            }
            else {
                pq.insert(w, 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;
    }
    
    public static void main(String[] args) {
        
        WeightedDigraph g = new WeightedDigraph("/Users/pauloser/Desktop/tinyEWG2.txt");
        System.out.println(g);
        
        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();
        DijkstraShortestPaths sp = new DijkstraShortestPaths(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) = " + String.format("%.3f", sp.distTo[v]));
    }
}