import java.util.*;

public class Dijkstra {

 
    public static void dijkstra(int[][] cost, int source) {
        int n = cost.length; 
        boolean[] visited = new boolean[n]; 
        double[] dist = new double[n]; 

        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        dist[source] = 0.0; 

        for (int count = 0; count < n - 1; count++) {
           
            int u = minDistance(dist, visited);
            visited[u] = true; 

       
            for (int v = 0; v < n; v++) {
               
                if (!visited[v] && cost[u][v] != 0 && dist[u] != Double.POSITIVE_INFINITY
                        && dist[u] + cost[u][v] < dist[v]) {
                    dist[v] = dist[u] + cost[u][v];
                }
            }
        }


        printSolution(dist);
    }


    private static int minDistance(double[] dist, boolean[] visited) {
        double min = Double.POSITIVE_INFINITY;
        int minIndex = -1;

        for (int v = 0; v < dist.length; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }


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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of vertices: ");
        int n = scanner.nextInt();

   
        int[][] cost = new int[n][n];
        System.out.println("Enter the adjacency matrix (enter 0 for no edge):");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cost[i][j] = scanner.nextInt();
            }
        }

        System.out.print("Enter the source vertex (0 to " + (n - 1) + "): ");
        int source = scanner.nextInt();

  
        dijkstra(cost, source);

        scanner.close();
    }
}

Algorithm ShortestPaths(v, cost, dist, n)
// dist[j], 1 ≤ j ≤ n, is set to the length of the shortest path 
// from vertex v to vertex j in a digraph G with n vertices. 
// dist[v] is set to zero. G is represented by its 
// cost adjacency matrix cost[1 : n, 1 : n].

for i := 1 to n do {
    // Initialize S and distances.
    S[i] := false;
    dist[i] := cost[v, i];
}
S[v] := true; dist[v] := 0.0; // Put v in S.

for num := 1 to n - 1 do {
    // Determine n - 1 shortest paths from v.
    Choose u from among those vertices not in S such that dist[u] is minimum;
    S[u] := true; // Put u in S.

    for (each w adjacent to u with S[w] = false) do {
        // Update distances.
        if (dist[w] > dist[u] + cost[u, w]) then
            dist[w] := dist[u] + cost[u, w];
    }
}