shortestpath

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();
    }
}

output:
Enter the number of vertices: 5
Enter the adjacency matrix (enter 0 for no edge):
0 4 0 0 0
0 0 1 0 0
0 0 0 2 0
0 0 0 0 3
0 0 0 0 0
Enter the source vertex (0 to 4): 0
Vertex Distance from Source
0                0.0
1                4.0
2                5.0
3                7.0
4                10.0