djikstra.java

import java.util.Arrays;

public class djikstra {
    public static int findMinDistance(int[] distance, boolean[] visited, int numberOfNodes) {
        int min = Integer.MAX_VALUE, minIndex = -1;

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

    public static void dijkstra(int[][] graph, int source, int numberOfNodes) {
        // Array to store the shortest distance from the source to each vertex
        int[] distance = new int[numberOfNodes];

        // To keep track of vertices included in the shortest path tree
        boolean[] visited = new boolean[numberOfNodes];

        // Initialize distances to infinity and visited[] to false
        Arrays.fill(distance, Integer.MAX_VALUE);
        Arrays.fill(visited, false);

        // Distance to the source is always 0
        distance[source] = 0;

        // Find shortest path for all vertices
        for (int count = 0; count < numberOfNodes - 1; count++) {
            // Pick the vertex with the minimum distance value not yet processed
            int u = findMinDistance(distance, visited, numberOfNodes);

            // Mark the picked vertex as processed
            visited[u] = true;

            // Update the distance of the adjacent vertices of the picked vertex
            for (int v = 0; v < numberOfNodes; v++) {
                // Update distance[v] only if:
                // - There's an edge from u to v
                // - v is not yet visited
                // - The new distance through u is smaller than the current distance
                if (graph[u][v] != 0 && !visited[v] && distance[u] != Integer.MAX_VALUE && distance[u] + graph[u][v] < distance[v]) {
                    distance[v] = distance[u] + graph[u][v];
                }
            }
        }

        // Print the constructed distance array
        printSolution(distance, numberOfNodes);
    }

    // Function to print the distances from the source to each vertex
    public static void printSolution(int[] distance, int numberOfNodes) {
        System.out.println("Vertex \t Distance from Source");
        for (int i = 0; i < numberOfNodes; i++) {
            System.out.println(i + " \t\t " + distance[i]);
        }
    }
}