Dijkstra Algorithm

//DijkstraAlgorithm 
import java.util.Scanner;
import java.util.Arrays;

public class DijkstraAlgorithm {

    // Method to find the vertex with the minimum distance value that hasn't been processed yet
    static int getMinDistanceVertex(int[] distance, boolean[] processedVertices, int numberOfVertices) {
        int minDistance = Integer.MAX_VALUE;  // Initialize with a large value
        int minVertexIndex = -1;  // Index of the vertex with the minimum distance

        // Search for the vertex with the smallest distance value
        for (int vertex = 0; vertex < numberOfVertices; vertex++) {
            if (!processedVertices[vertex] && distance[vertex] <= minDistance) {
                minDistance = distance[vertex];  // Update minimum distance
                minVertexIndex = vertex;  // Update index of vertex with minimum distance
            }
        }
        return minVertexIndex;
    }

    // Method to implement Dijkstra's algorithm to find the shortest path from the source
    static void dijkstra(int[][] graph, int[] distance, boolean[] processedVertices, int numberOfVertices, int sourceVertex) {
        // Initialize distances and processedVertices
        Arrays.fill(distance, Integer.MAX_VALUE);  // Set all distances to infinity initially
        Arrays.fill(processedVertices, false);  // Mark all vertices as unprocessed

        distance[sourceVertex] = 0;  // Distance from source to itself is 0

        // Find the shortest path for all vertices
        for (int i = 0; i < numberOfVertices - 1; i++) {
            // Get the vertex with the minimum distance value that hasn't been processed yet
            int currentVertex = getMinDistanceVertex(distance, processedVertices, numberOfVertices);

            // Mark the current vertex as processed
            processedVertices[currentVertex] = true;

            // Update distance values of adjacent vertices of the current vertex
            for (int adjacentVertex = 0; adjacentVertex < numberOfVertices; adjacentVertex++) {
                // If the adjacent vertex is unprocessed, has a path from currentVertex, and distance can be minimized
                if (!processedVertices[adjacentVertex] && graph[currentVertex][adjacentVertex] != 0 &&
                        distance[currentVertex] != Integer.MAX_VALUE &&
                        distance[currentVertex] + graph[currentVertex][adjacentVertex] < distance[adjacentVertex]) {
                    // Update the distance to the adjacent vertex
                    distance[adjacentVertex] = distance[currentVertex] + graph[currentVertex][adjacentVertex];
                }
            }
        }
    }

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

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

        // Taking input for number of vertices
        System.out.print("Enter the number of vertices: ");
        int numberOfVertices = sc.nextInt();

        // Initialize the graph matrix (adjacency matrix)
        int[][] graph = new int[numberOfVertices][numberOfVertices];

        // Taking input for the adjacency matrix (graph)
        System.out.println("Enter the adjacency matrix (0 means no edge between vertices):");
        for (int i = 0; i < numberOfVertices; i++) {
            for (int j = 0; j < numberOfVertices; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // Taking input for the source vertex
        System.out.print("Enter the source vertex: ");
        int sourceVertex = sc.nextInt();

        // Arrays to store the distance and processed status of vertices
        int[] distance = new int[numberOfVertices];
        boolean[] processedVertices = new boolean[numberOfVertices];

        // Run Dijkstra's algorithm starting from the source vertex
        dijkstra(graph, distance, processedVertices, numberOfVertices, sourceVertex);

        // Print the shortest distances from the source vertex
        printSolution(distance, numberOfVertices);
    }
}

/*
Test Case
Enter the number of vertices: 5
Enter the adjacency matrix (0 means no edge between vertices):
0 10 0 0 0
0 0 5 0 0
0 0 0 15 0
0 0 0 0 20
0 0 0 0 0
Enter the source vertex: 0
Vertex   Distance from Source
0        0
1        10
2        15
3        30
4        50
*/