import java.util.*;

public class Dijkstra
{
    private int size;
    private ArrayList<Integer> gevondenPad = new ArrayList<Integer>();
   
    public Dijkstra(int x)
    {
        size = x;
    }
    
    public void zoek(int[][] matrix, int beginPunt, int eindPunt)
    {
        int graaf[][] = matrix;
        boolean nietKlaar = true;
        boolean padAanwezig = true;
        int nodeNietInS;
        int tempArray1[] = new int[size];
        int tempArray2[][] = new int[2][size];
       
        for (int i=0; i<size; i++) 
        {
            tempArray1[i] = 0;
            tempArray2[0][i] = Integer.MAX_VALUE;
            tempArray2[1][i] = -1;
        }

        tempArray1[beginPunt] = 1;
        tempArray2[0][beginPunt] = 0;
        tempArray2[1][beginPunt] = beginPunt;
        for (int i=0; i<size; i++) 
        {
            if ((beginPunt != i) && (graaf[beginPunt][i] > -1)) 
            { 
                tempArray2[0][i] = graaf[beginPunt][i];
                tempArray2[1][i] = beginPunt;
            }
        }
        
                
        while (nietKlaar && padAanwezig) 
        {                
            int minT = Integer.MAX_VALUE;
            int v = -1;
            for (int i=0; i<size; i++) 
            {
                if ((tempArray1[i] == 0) && (tempArray2[0][i] < minT)) 
                {
                    minT = tempArray2[0][i];
                    v = i;
                }
            }
            
            tempArray1[v] = 1;
            nodeNietInS = -1;
            for (int i=0; i<size; i++) 
            {
                if ((tempArray1[i] == 0) && (graaf[v][i] > -1)) 
                {
                    if ((tempArray2[0][v] + graaf[v][i]) < tempArray2[0][i]) 
                    {
                        tempArray2[0][i] = tempArray2[0][v] + graaf[v][i];
                        tempArray2[1][i] = v;
                    }
                }
            }
            
            if (tempArray1[eindPunt] == 1)  
                nietKlaar = false;
            else 
            {
                nietKlaar = true;
                padAanwezig = false;
                for (int i=0; i<size; i++) 
                {
                    if ((tempArray1[i]==0) && (tempArray2[0][i] < Integer.MAX_VALUE))
                    {
                        padAanwezig = true;
                    }
                }
            }
        }
        
        int n = eindPunt;
        gevondenPad.add(n+1);
    
        n = tempArray2[1][eindPunt];
        while(n != beginPunt) 
        {
            gevondenPad.add(n+1);
            n = tempArray2[1][n];
        }
        gevondenPad.add(n+1);

        for (int i=gevondenPad.size()-1; 0<=i; i--)
        {
            System.out.print(gevondenPad.get(i) + " ");
        }
        
        System.out.print("met afstand: " + tempArray2[0][19]);
    }
}