package matrix;

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{

	static int N= 4;
	static int dim = N*N;

    static final int V=dim;

    static void propagazione(int matrix[][], int x) {
    	for(int j=0; j<dim; j++) {
        	for(int i=0; i<dim; i++) {
        		if(matrix[x][i]==j) {
        			System.out.print(i + ", ");
        		}
        	}
        	System.out.println("----------------------");
    	}

    	return;
    }

    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    int[] dijkstra(int graph[][], int src)
    {

        Boolean sptSet[] = new Boolean[V];
        int[] dist = new int[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        //printSolution(dist, V);
        return dist;
    }

    public static void main (String[] args)
    {

		int[][] matrice = new int[dim][dim];


		for(int i =0; i < dim; i++) {
			for(int j=0; j<dim; j++) {
				if(i==j) matrice[i][j]=0;
				else {
					if(Math.abs(i-j)==1)
						if(i%N==0 && j==i-1) matrice[i][j]=0;
						else if(j%N==0 && i==j-1) matrice[i][j]=0;
						else 						matrice[i][j]=1;
					else if(Math.abs(i-j)==N) matrice[i][j]=1;
					else matrice[i][j]=0;
				}
			}
		}

		for (int i = 0; i < matrice.length; i++) {
		    for (int j = 0; j < matrice[i].length; j++) {
		        System.out.print(matrice[i][j] + "," + " ");
		    }
		    System.out.println();
		}

		System.out.println("--------------------------------------");

		//int[] riga= new int[dim];
		int[][] fire= new int[dim][dim];
        ShortestPath t = new ShortestPath();
        for(int i=0; i<dim; i++) {
        	fire[i]= t.dijkstra(matrice, i);

        }

		for (int i = 0; i < fire.length; i++) {
		    for (int j = 0; j < fire[i].length; j++) {
		        System.out.print(fire[i][j] + "," + " ");
		    }
		    System.out.println();
		}
		System.out.println("--------------------------------------");
		propagazione(fire,10);

    }
}