import java.util.*;


class GrafLost {


    private ArrayList<Node> nodeListe;
    private ArrayList<Kant> kantListe;
    private int storrelse;


    public GrafLost(){
        nodeListe = new ArrayList<Node>();
        kantListe = new ArrayList<Kant>();
    }


    public void finnKortesteVeiFra(String node){

        Node start = finnNode(node);
        dijkstra(start);
    }

    private void dijkstra(Node start){

        //1.
        //Sette avstand for alle noder lik uendelig,
        //og sette avstand for startnode lik 0.
        for (Node n : nodeListe){
            n.avstand = Integer.MAX_VALUE;
        }
        start.avstand = 0;


        //2.
        //Lag en PQ eller liste der Nodene sorteres etter "avstand"
        //legg til startnoden i listen.
        ArrayList<Node> q = new ArrayList<Node>();
        q.add(start);

        //3.
        //S? lenge listen ikke er tom:
        //Ta ut node med den minste kjente "avstand".
        //oppdater kjent avstand til alle naboer.
        while (q.size() > 0){

            Node denne = hentMinsteNodeOgOppdaterKanter(q);
            q.remove(denne);


        }

    }


    private Node hentMinsteNodeOgOppdaterKanter(ArrayList<Node> liste){

        Node minste = liste.get(0);

        for (Node n : liste){

            if (n.avstand < minste.avstand){
                minste = n;
            }
        }

        System.out.println("N? BES?KER JEG: " + minste.navn + ". BESTE VEI: " + minste.avstand);

        for (Kant k : minste.listeKanter){

            Node til = k.til;
            int avstand = k.vekt + minste.avstand;

            if (avstand < til.avstand){

                System.out.println("OPPDATERER POTENSIELL AVSTAND FRA " + minste.navn + " til " + til.navn + ", vekt: " + avstand);

                til.avstand = avstand;

                if (!til.lagtTilIListe){
                    liste.add(til);
                }
                til.lagtTilIListe = true;

            }
        }

        return minste;
    }



    public void leggTilNode(String navn){

        Node ny = new Node(navn);
        nodeListe.add(ny);
    }


    public void leggTilKant(String en, String to, int vekt){

        Node node1 = finnNode(en);
        Node node2 = finnNode(to);
        Kant ny1 = new Kant(node1, node2, vekt);
        Kant ny2 = new Kant(node2, node1, vekt);
        kantListe.add(ny1);
        kantListe.add(ny2);
        node1.listeKanter.add(ny1);
        node2.listeKanter.add(ny2);
    }


    private Node finnNode(String navn){

        for (Node n: nodeListe){
            if (n.navn.equals(navn)){
                return n;
            }
        }
        return null;
    }


    private class Node{

        private String navn;
        private int avstand;
        private boolean lagtTilIListe;
        private ArrayList<Kant> listeKanter;

        public Node(String navn){
            listeKanter = new ArrayList<Kant>();
            this.navn = navn;
            lagtTilIListe = false;
        }
    }

    private class Kant{

        private Node fra;
        private Node til;
        private int vekt;

        public Kant(Node fra, Node til, int vekt){
            this.fra = fra;
            this.til = til;
            this.vekt = vekt;
        }
    }
}