// Dijksras.java

// Represents an weighted, undirected graph
class Graph<Type> {
    // the matrix stores the edge information
    private int[][] matrix;

    // this stores the values being stored by this graph
    private Type[] values;

    // the size of the graph
    private int size;

    // set the graph as empty
    public Graph(int size) {
        matrix = new int[size][size];
        this.size = size;

        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                matrix[i][j] = Integer.MAX_VALUE;
            }
        }

        // make space for the values (and ignore the cast warning)
        @SuppressWarnings("unchecked")
        Type[] values = (Type[]) new Object[size];
        this.values = values;
    }

    // lookup a node number by value
    public int lookup(Type value) {
        for (int i = 0; i < size; i++) {
            if (values[i].equals(value)) {
                return i;
            }
        }
        return -1;
    }

    // insert an edge by index -- in both directions
    public void insertEdge(int from, int to, int cost) {
        matrix[from][to] = cost;
        matrix[to][from] = cost;
    }

    // insert an edge by value
    public void insertEdge(Type from, Type to, int cost) {
        int fromIndex = lookup(from);
        int toIndex = lookup(to);
        insertEdge(fromIndex, toIndex, cost);
    }

    // remove an edge -- again both directions
    public void removeEdge(int from, int to) {
        matrix[from][to] = 0;
        matrix[to][from] = 0;
    }

    // return the cost of an edge or 0 for none
    public int getCost(int from, int to) {
        return matrix[from][to];
    }

    // add a node's data to the graph
    public void setValue(int node, Type value) {
        values[node] = value;
    }
    
    // return the size of the graph
    public int getSize() {
        return size;
    }

    // get the value of a node
    public Type getValue(int index) {
        return values[index];
    }
}

// this heap is used to keep track of the nodes used by
// Dijksra's algorithm -- it stores the node index and the
// tentative cost
class NodeHeap {
    private class Node {
        public int index;
        public int tentative_cost;
        
        public Node(int index, int tentative_cost) {
            this.index = index;
            this.tentative_cost = tentative_cost;
        }
    }

    private Node[] array;
    private int count;

    // start with nothing
    public NodeHeap(int size) {
        array = new Node[size];
        count = 0;
    }

    // find the left child of a node
    public int left(int node) {
        return 2 * node  + 1;
    }

    // find the right child of a node
    public int right(int node) {
        return 2 * node  + 2; 
    }

    // find the parent of a node
    public int parent(int node) {
        return (node - 1) / 2;
    }

    // insert an item into the heap
    public void insert(int index, int tentative_cost) {
        // put item in next available slot
        array[count] = new Node(index, tentative_cost);

        // keep indices into node we inserted and its parent
        int node = count;
        int p = parent(node);

        // increment total number of items
        count++;

        // upheap until it's root, or parent is smaller (using cost)
        while ((node != 0) && (array[node].tentative_cost < array[p].tentative_cost)) {
            // swap values
            Node temp = array[node];
            array[node] = array[p];
            array[p] = temp;

            // update indices
            node = p;
            p = parent(node);
        }
    }

    // remove the top item -- returns the index of the node
    public int dequeue() {
        // set aside root
        int retValue = array[0].index;

        // move last value to the root
        array[0] = array[count - 1];
        count--;

        // find the children
        int node = 0;
        int l = left(node);
        int r = right(node);

        // while one child is smaller than us
        while ((l < count) && (array[l].tentative_cost < array[node].tentative_cost) ||
               (r < count) && (array[r].tentative_cost < array[node].tentative_cost)) {

            // find smallest child
            int min;
            if (l < count && r < count) {
                if (array[l].tentative_cost < array[r].tentative_cost) {
                    min = l;
                } else {
                    min = r;
                }
            } else {
                min = l;
            }

            // swap with the smallest child
            Node temp = array[node];
            array[node] = array[min];
            array[min] = temp;

            // update indices
            node = min;
            l = left(node);
            r = right(node);
        }
        
        // return orig. root
        return retValue;
    }

    // return the smallest item in the heap
    public int min() {
        return array[0].index;
    }

    public int getCount() {
        return count;
    }
}


public class Dijkstras {
    // use Dijkstra's algorithm to find a shortest path
    public static int shortestPath(Graph<String> graph, String startcity, String endcity) {
        // find the city names indices
        int start = graph.lookup(startcity);
        int end = graph.lookup(endcity);

        // the size of the graph
        int N = graph.getSize();

        // keep track of the tentative distances
        int[] tentative = new int[N];
        for (int i = 0; i < N; i++) {
            tentative[i] = Integer.MAX_VALUE;
        }
        tentative[start] = 0;

        // make the heap of nodes we are using
        NodeHeap nodes = new NodeHeap(N);
    
        // insert the start city with cost 0
        nodes.insert(start, 0);
        
        // while our heap of nodes isn't empty
        while (nodes.getCount() > 0) {
            // get the next node to consider
            int current = nodes.dequeue();

            // for each neighbor of the current node
            for (int neighbor = 0; neighbor < N; neighbor++) {
                if (graph.getCost(current, neighbor) < Integer.MAX_VALUE) {
                    
                    // calculate distance from start to neighbor through current
                    int distance = tentative[current] + graph.getCost(current, neighbor);

                    // if this is less than the what we have so far
                    if (distance < tentative[neighbor]) {
                        // update the distance
                        tentative[neighbor] = distance;

                        // add it to the heap (it may already be there w/ a bigger cost)
                        nodes.insert(neighbor, distance);

                        // print it out so we can see algorithm working
                        System.out.println("Distance from " + graph.getValue(start) +
                                " to " + graph.getValue(neighbor) + " is " + distance);
                    }
                }
            }
        }

        // return the tentative cost to the final node (which is now official)
        return tentative[end];
    }

    public static void main(String args[]) {
        // create a graph with the cities
        Graph<String> graph = new Graph<String>(11);
        graph.setValue(0, "Alexandria");
        graph.setValue(1, "Blacksburg");
        graph.setValue(2, "Charlottesville");
        graph.setValue(3, "Danville");
        graph.setValue(4, "Fredericksburg");
        graph.setValue(5, "Harrisonburg");
        graph.setValue(6, "Lynchburg");
        graph.setValue(7, "Newport News");
        graph.setValue(8, "Richmond");
        graph.setValue(9, "Roanoke");
        graph.setValue(10, "Virginia Beach");

        graph.insertEdge("Alexandria", "Fredericksburg", 50);
        graph.insertEdge("Fredericksburg", "Richmond", 60);
        graph.insertEdge("Richmond", "Charlottesville", 70);
        graph.insertEdge("Richmond", "Lynchburg", 110);
        graph.insertEdge("Richmond", "Danville", 145);
        graph.insertEdge("Richmond", "Newport News", 70);
        graph.insertEdge("Newport News", "Virginia Beach", 35);
        graph.insertEdge("Virginia Beach", "Danville", 210);
        graph.insertEdge("Danville", "Lynchburg", 70);
        graph.insertEdge("Lynchburg", "Charlottesville", 70);
        graph.insertEdge("Lynchburg", "Roanoke", 65);
        graph.insertEdge("Roanoke", "Blacksburg", 40);
        graph.insertEdge("Blacksburg", "Harrisonburg", 140);
        graph.insertEdge("Harrisonburg", "Alexandria", 135);
        graph.insertEdge("Harrisonburg", "Charlottesville", 50);

        System.out.println("\nDistance is " + shortestPath(graph, "Fredericksburg", "Blacksburg"));
    }
}