Untitled

import java.util.Arrays;

public class Main {

    private static final int INF = Integer.MAX_VALUE;

    public void dijkstra(int[][] graph, int source, int destination) {
        int n = graph.length;
        int[] dist = new int[n]; // array to store shortest distances
        boolean[] visited = new boolean[n]; // array to mark visited nodes
        int[] pred = new int[n]; // array to store predecessors

        Arrays.fill(dist, INF); // initialize distances as infinity
        dist[source] = 0; // distance from source to source is 0

        for (int i = 0; i < n - 1; i++) {
            // select the vertex with the minimum distance
            int u = minDistance(dist, visited);
            visited[u] = true; // mark the vertex as visited

            // update distances of adjacent vertices
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pred[v] = u; // store predecessor
                }
            }
        }
        printShortestPath(source, destination, dist, pred); // print the shortest path and distance
    }

    // helper function to find the vertex with the minimum distance
    private int minDistance(int[] dist, boolean[] visited) {
        int minDist = INF;
        int minVertex = -1;

        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minVertex = i;
            }
        }
        return minVertex;
    }

    // helper function to print the shortest path and distance
    private void printShortestPath(int source, int destination, int[] dist, int[] pred) {
        System.out.print("Shortest path from " + source + " to " + destination + ": ");
        if (dist[destination] == INF) {
            System.out.println("No path exists.");
            return;
        }
        printPath(pred, destination);
        System.out.println("= " + dist[destination]);
    }

    // helper function to print the path from source to destination vertex
    private void printPath(int[] pred, int dest) {
        if (pred[dest] != -1) {
            printPath(pred, pred[dest]);
            System.out.print("-" + dest);
        } else {
            System.out.print(dest);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, 0, 1, 0},
                {2, 0, 4, 3, 0},
                {0, 4, 0, 0, 6},
                {1, 3, 0, 0, 5},
                {0, 0, 6, 5, 0},
        };
        Main dijkstra = new Main();
        dijkstra.dijkstra(graph, 0, 4); // Call dijkstra method with source and destination vertices
    }
}