/**
 *
 * This demo program simulates dijkstra's algorithm described in the article.
 * below is a sample output of this program:
 *
 * -----------------------------------------------------
 * finding shortest path from [g] to [f]
 * g has been selected. finding all neighbors...
 *       g->b [1.0] [b added to open list]
 *       g->d [2.0] [d added to open list]
 *       g->h [0.5] [h added to open list]
 * g has been moved to closed list.
 * h has been selected. finding all neighbors...
 *       neighbor d is already in open list.
 *       h->d [1.0] is a shorter path!
 * h has been moved to closed list.
 * b has been selected. finding all neighbors...
 *       b->a [2.0] [a added to open list]
 *       b->c [3.0] [c added to open list]
 * b has been moved to closed list.
 * d has been selected. finding all neighbors...
 *       neighbor c is already in open list.
 *       d->c [2.0] is a shorter path!
 *       d->e [2.0] [e added to open list]
 * d has been moved to closed list.
 * a has been selected. finding all neighbors...
 *       neighbor e is already in open list.
 *       a->f [3.0] [f added to open list]
 * a has been moved to closed list.
 * c has been selected. finding all neighbors...
 * c has been moved to closed list.
 * e has been selected. finding all neighbors...
 *       neighbor f is already in open list.
 * e has been moved to closed list.
 * f has been selected. finding all neighbors...
 * f has been moved to closed list.
 * tracing from [f] to [g]
 * f->a->b->g
 * -----------------------------------------------------
 *
 * code was not written to be professional but for readability. 
 *
 * www.tech-algorithm.com
 *
 */

import java.util.Iterator;
import java.util.LinkedList;

public class DijkstraAlgorithm {
        
    public DijkstraAlgorithm() {
        
        LinkedList open = new LinkedList() ;
        LinkedList closed = new LinkedList() ;
        
        // Node is a custom class made just for this demo
        // by default all nodes is neither in open or closed list
        Node a,b,c,d,e,f,g,h ;
        
        a = new Node("a") ;
        b = new Node("b") ;
        c = new Node("c") ;
        d = new Node("d") ;
        e = new Node("e") ;
        f = new Node("f") ;
        g = new Node("g") ;
        h = new Node("h") ;
        
        // connect nodes according to connections from the article
        // the floating numbers are the movement costs
        a.connectNode(b,1.0f) ;
        a.connectNode(e,2.0f) ;
        a.connectNode(f,1.0f) ;
        b.connectNode(g,1.0f) ;
        b.connectNode(c,2.0f) ;
        c.connectNode(d,1.0f) ;
        d.connectNode(e,1.0f) ;
        d.connectNode(g,2.0f) ;
        d.connectNode(h,0.5f) ;
        e.connectNode(f,2.0f) ;
        g.connectNode(h,0.5f) ;
        
        // we want to finding the shortest path from node g to node f
        Node start = g ;
        Node end = f ;
        
        // shortest path from start -> end
        // put first node in the open list
        System.out.println("finding shortest path from ["+start.getName()+"] to ["+end.getName()+"]") ;
        start.setOpen(true) ;
        open.add(start) ;
        while (true) {
                        
            Iterator o = open.listIterator() ;
            
            // if there is no more item in the open list, the search is done
            if (!o.hasNext()) break ;
            
            // get the lowest overall cost node from open list
            Node node = (Node)o.next() ;            
            while (o.hasNext()) {
                Node temp = (Node)o.next() ;
                if (temp.getOverallCost()<node.getOverallCost())
                    node = temp ;
            }
            System.out.println(node.getName()+" has been selected. finding all neighbors...") ;
            // find all immediate neighbors of selected node
            Iterator n = node.getNeighbors() ;
            while (n.hasNext()) {
                Path path = (Path)n.next() ;                
                Node endNode = path.getEndNode(node) ;                
                if (endNode.isClosed()) continue ;
                if (!endNode.isOpen()) {
                    // add to open list
                    endNode.setOpen(true) ;
                    endNode.setParent(node) ;
                    endNode.setOverallCost(
                            node.getOverallCost()+endNode.getOverallCost()+path.getCost()) ;                    
                    open.add(endNode) ;
                    System.out.println("\t"+node.getName()+"->"+endNode.getName()+
                            " ["+endNode.getOverallCost()+"] ["+ endNode.getName()+" added to open list]") ;
                } else {
                    // check if this path is shorter than previous
                    System.out.println("\tneighbor "+endNode.getName()+" is already in open list.") ;
                    if ((node.getOverallCost() + path.getCost()) < endNode.getOverallCost()) {                        
                        endNode.setParent(node) ;
                        endNode.setOverallCost(
                                node.getOverallCost()+path.getCost()) ;
                        System.out.println("\t"+node.getName()+"->"+endNode.getName()+
                                " ["+endNode.getOverallCost()+"] is a shorter path!") ;
                    }
                }
            }
            
            // put selected node to closed list
            node.setClosed(true) ;
            closed.add(node) ;
            open.remove(node) ;
            System.out.println(node.getName()+" has been moved to closed list.") ;                        
            
            // once target (end node) put into closed list the search is done
            if (node.equals(end)) break ;
        }
        
        // now trace back from [end] -> [start] by parent
        System.out.println("tracing from ["+end.getName()+"] to ["+start.getName()+"]") ;        
        Node prev = end.getParent() ;                
        String line = end.getName() ;
        while (prev != null) {         
            line = line + "->"+prev.getName() ;
            end = prev ;
            prev = prev.getParent() ;            
        }        
        System.out.println(line) ;
    }
    
    public class Node {        
        private String name ;
        private Node parent ;
        private float overallCost ;
        private LinkedList paths ;
        private boolean open, closed ;
        
        public Node(String name) {            
            this.name = name ;
            parent = null ;
            overallCost = 0.0f ;
            paths = new LinkedList() ;
            setOpen(false) ;
            setClosed(false) ;
        }
        
        public void connectNode(Node toNode,float cost) {
            // check if already connected to avoid duplicate connection
            Iterator i = paths.listIterator() ;
            Path path ;
            while (i.hasNext()) {
                path = (Path)i.next() ;
                if ((path.getEndA().equals(toNode)) || (path.getEndB().equals(toNode))) {
                    System.out.println(getName()+" is already connected to "+toNode.getName()) ;
                    return ; // already connected to the node
                }
            }
            
            // connect this node with toNode
            path = new Path(this, toNode, cost) ;
            paths.add(path) ;
            toNode.addPath(path) ;
        }
        
        public void addPath(Path path) {
            // check if path already exist to avoid duplicate
            Iterator i = paths.listIterator() ;
            while (i.hasNext()) {
                Path p = (Path)i.next() ;
                if (p.equals(path)) {
                    System.out.println("The path already exists!") ;
                    return ;
                }
            }
            
            paths.add(path) ;
        }
        
        public Iterator getNeighbors() {
            return paths.listIterator() ;
        }
        
        public void setParent(Node newParent) {
            parent = newParent ;
        }
        
        public Node getParent() {
            return parent ;
        }
        
        public void setOverallCost(float newCost) {
            overallCost = newCost ;
        }
        
        public float getOverallCost() {
            return overallCost ;
        }

        public boolean isOpen() {
            return open;
        }

        public void setOpen(boolean open) {
            this.open = open;
        }

        public boolean isClosed() {
            return closed;
        }

        public void setClosed(boolean closed) {
            this.closed = closed;
        }

        public String getName() {
            return name;
        }
    }
    
    public class Path {
        private Node endA, endB ;
        private float cost ;
        public Path(Node endA, Node endB, float cost) {
            this.endA = endA ;
            this.endB = endB ;
            this.cost = cost ;
        }
        public float getCost() {
            return cost ;
        }
        public Node getEndA() {
            return endA ;
        }
        public Node getEndB() {
            return endB ;
        }
        public Node getEndNode(Node startNode) {
            if (endA.equals(startNode))
                return endB ;
            if (endB.equals(startNode))
                return endA ;
            return null ;
        }
    }
    
    public static void main(String[] args) {
        
        new DijkstraAlgorithm() ;
        
    }
    
}