Dijkstra's Algorithm

import java.util.*;

public class DijkstraAlgorithm {
    
    // Find shortest distances from start to all nodes
    public static int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] distances = new int[n];
        boolean[] visited = new boolean[n];
        
        // Initialise all distances to "infinity"
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;
        
        // Priority queue: {distance, node}
        PriorityQueue<int[]> queue = 
            new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        queue.offer(new int[]{0, start});
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int dist = current[0], node = current[1];
            
            if (visited[node]) continue;
            visited[node] = true;
            
            // Check all neighbours
            for (int next = 0; next < n; next++) {
                if (graph[node][next] > 0 && !visited[next]) {
                    int newDist = dist + graph[node][next];
                    if (newDist < distances[next]) {
                        distances[next] = newDist;
                        queue.offer(new int[]{newDist, next});
                    }
                }
            }
        }
        return distances;
    }
}

public class Main {
    public static void main(String[] args) {
        // Adjacency matrix — 0 means no direct connection
        //          A  B  C  D  E  F  H
        int[][] graph = {
            {0, 2, 1, 0, 0, 0, 0},  // A
            {2, 0, 0, 1, 3, 0, 0},  // B
            {1, 0, 0, 3, 0, 6, 0},  // C
            {0, 1, 3, 0, 0, 0, 0},  // D
            {0, 3, 0, 0, 0, 5, 0},  // E
            {0, 0, 6, 0, 5, 0, 2},  // F
            {0, 0, 0, 0, 0, 2, 0}   // H
        };
        String[] nodes = {"A","B","C","D","E","F","H"};
        
        int[] distances = DijkstraAlgorithm.dijkstra(graph, 0);
        
        // Print shortest distances from A
        for (int i = 0; i < nodes.length; i++) {
            System.out.println("A → " + nodes[i] + " = " + distances[i]);
        }
        // Output: A → H = 9
    }
}