Dijkstra’s Algorithm

Problem Statement

Write a Java program that implements Dijkstra’s algorithm for a weighted graph using a priority queue. Represent the graph as an adjacency list, where each edge has a non-negative weight, and compute the shortest path distances from a source node to all other nodes. The program should handle directed graphs and print the shortest distances for each reachable node. Test the implementation with various graph structures, including connected, sparse, and dense graphs, as well as edge cases like single nodes or unreachable nodes. You can visualize this as finding the shortest driving routes from a starting city to all other cities, using a priority queue to always explore the closest unvisited city next.

Input:

• Number of nodes n (1 ≤ n ≤ 10^5).
• List of edges as triples [u, v, w] (node u to node v with weight w, w ≥ 0).
• Source node for shortest paths (0 ≤ source < n). Output: A string of node indices and their shortest distances from the source (e.g., "0:0 1:3 2:5"), or "INF" for unreachable nodes. Constraints:
• Nodes are integers from 0 to n-1.
• Edge weights are non-negative integers (0 ≤ w ≤ 10^9).
• The graph may be disconnected; unreachable nodes have distance "INF".
• Assume the input graph is valid (no negative weights). Example:
• Input: n=4, edges=[[0,1,1], [0,2,4], [1,2,2], [1,3,6]], source=0
• Output: "0:0 1:1 2:3 3:7"
• Explanation: Shortest paths from node 0: 0→1 (1), 0→1→2 (1+2=3), 0→1→3 (1+6=7).
• Input: n=3, edges=[[0,1,2]], source=2
• Output: "0:INF 1:INF 2:0"
• Explanation: Node 2 cannot reach 0 or 1; only 2 is reachable (distance 0).

Pseudocode

CLASS NodeDistance
    SET node to integer
    SET distance to long
ENDCLASS

CLASS MinPriorityQueue
    SET array to new NodeDistance array of size 1000
    SET size to 0
    
    FUNCTION enqueue(node, distance)
        IF size equals array length THEN
            RETURN false
        ENDIF
        SET array[size] to new NodeDistance(node, distance)
        CALL siftUp(size)
        INCREMENT size
        RETURN true
    ENDFUNCTION
    
    FUNCTION siftUp(index)
        WHILE index > 0
            SET parent to (index - 1) / 2
            IF array[index].distance >= array[parent].distance THEN
                BREAK
            ENDIF
            SWAP array[index] and array[parent]
            SET index to parent
        ENDWHILE
    ENDFUNCTION
    
    FUNCTION dequeue()
        IF size equals 0 THEN
            RETURN null
        ENDIF
        SET result to array[0]
        SET array[0] to array[size - 1]
        DECREMENT size
        IF size > 0 THEN
            CALL siftDown(0)
        ENDIF
        RETURN result
    ENDFUNCTION
    
    FUNCTION siftDown(index)
        SET minIndex to index
        WHILE true
            SET left to 2 * index + 1
            SET right to 2 * index + 2
            IF left < size AND array[left].distance < array[minIndex].distance THEN
                SET minIndex to left
            ENDIF
            IF right < size AND array[right].distance < array[minIndex].distance THEN
                SET minIndex to right
            ENDIF
            IF minIndex equals index THEN
                BREAK
            ENDIF
            SWAP array[index] and array[minIndex]
            SET index to minIndex
        ENDWHILE
    ENDFUNCTION
ENDCLASS

FUNCTION dijkstra(n, edges, source)
    CREATE adjList as new list of lists of (node, weight) pairs for n nodes
    FOR each edge [u, v, w] in edges
        ADD (v, w) to adjList[u]
    ENDFOR
    CREATE distances as array of size n, initialized to INF
    SET distances[source] to 0
    CREATE queue as new MinPriorityQueue
    ENQUEUE (source, 0) to queue
    CREATE visited as boolean array of size n, initialized to false
    WHILE queue is not empty
        SET nodeDist to queue.dequeue()
        SET node to nodeDist.node
        SET dist to nodeDist.distance
        IF visited[node] THEN
            CONTINUE
        ENDIF
        SET visited[node] to true
        FOR each (neighbor, weight) in adjList[node]
            IF dist + weight < distances[neighbor] THEN
                SET distances[neighbor] to dist + weight
                ENQUEUE (neighbor, dist + weight) to queue
            ENDIF
        ENDFOR
    ENDWHILE
    CREATE result as new StringBuilder
    FOR i from 0 to n-1
        IF distances[i] equals INF THEN
            APPEND i + ":INF" to result
        ELSE
            APPEND i + ":" + distances[i] to result
        ENDIF
        IF i < n-1 THEN
            APPEND " " to result
        ENDIF
    ENDFOR
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of graphs (n, edges, source)
    FOR each testCase in testCases
        PRINT test case details
        CALL dijkstra(testCase.n, testCase.edges, testCase.source)
        PRINT shortest distances
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a NodeDistance class to store a node index and its tentative distance.
2. Define a MinPriorityQueue class using a min-heap with: a. An array to store NodeDistance objects, prioritized by distance. b. enqueue: Add node-distance pair, sift up to maintain min-heap. c. siftUp: Move smaller distance up. d. dequeue: Remove root (smallest distance), sift down. e. siftDown: Move larger distance down.
3. In dijkstra: a. Build adjacency list from edges (directed: add u→v,w). b. Initialize distances to INF, except source (0). c. Enqueue source with distance 0. d. While queue is not empty:
   • Dequeue node with smallest distance.
   • Skip if visited.
   • Mark node visited.
   • Update neighbors’ distances if shorter path found, enqueue them. e. Format distances as string (INF for unreachable).
4. In main, test with different graph structures and edge cases.

Java Implementation

import java.util.*;

public class DijkstrasAlgorithm {
    // Class to store node and distance pair
    static class NodeDistance {
        int node;
        long distance;

        NodeDistance(int node, long distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    // Custom min-heap priority queue for node-distance pairs
    static class MinPriorityQueue {
        private NodeDistance[] array;
        private int size;
        private static final int DEFAULT_SIZE = 1000;

        public MinPriorityQueue() {
            array = new NodeDistance[DEFAULT_SIZE];
            size = 0;
        }

        public boolean enqueue(int node, long distance) {
            if (size == array.length) {
                return false; // Queue full
            }
            array[size] = new NodeDistance(node, distance);
            siftUp(size);
            size++;
            return true;
        }

        private void siftUp(int index) {
            while (index > 0) {
                int parent = (index - 1) / 2;
                if (array[index].distance >= array[parent].distance) {
                    break;
                }
                // Swap
                NodeDistance temp = array[index];
                array[index] = array[parent];
                array[parent] = temp;
                index = parent;
            }
        }

        public NodeDistance dequeue() {
            if (size == 0) {
                return null; // Queue empty
            }
            NodeDistance result = array[0];
            array[0] = array[size - 1];
            size--;
            if (size > 0) {
                siftDown(0);
            }
            return result;
        }

        private void siftDown(int index) {
            int minIndex = index;
            while (true) {
                int left = 2 * index + 1;
                int right = 2 * index + 2;
                if (left < size && array[left].distance < array[minIndex].distance) {
                    minIndex = left;
                }
                if (right < size && array[right].distance < array[minIndex].distance) {
                    minIndex = right;
                }
                if (minIndex == index) {
                    break;
                }
                // Swap
                NodeDistance temp = array[index];
                array[index] = array[minIndex];
                array[minIndex] = temp;
                index = minIndex;
            }
        }
    }

    // Dijkstra’s algorithm to find shortest paths
    public String dijkstra(int n, int[][] edges, int source) {
        // Build adjacency list
        List<List<int[]>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(new int[]{edge[1], edge[2]}); // Directed: u -> v, weight
        }

        // Initialize distances and priority queue
        long[] distances = new long[n];
        Arrays.fill(distances, Long.MAX_VALUE);
        distances[source] = 0;
        MinPriorityQueue queue = new MinPriorityQueue();
        queue.enqueue(source, 0);
        boolean[] visited = new boolean[n];

        // Process nodes
        while (true) {
            NodeDistance nodeDist = queue.dequeue();
            if (nodeDist == null) break;
            int node = nodeDist.node;
            long dist = nodeDist.distance;

            if (visited[node]) continue;
            visited[node] = true;

            for (int[] neighbor : adjList.get(node)) {
                int v = neighbor[0];
                long w = neighbor[1];
                if (dist + w < distances[v]) {
                    distances[v] = dist + w;
                    queue.enqueue(v, dist + w);
                }
            }
        }

        // Format output
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (distances[i] == Long.MAX_VALUE) {
                result.append(i).append(":INF");
            } else {
                result.append(i).append(":").append(distances[i]);
            }
            if (i < n - 1) result.append(" ");
        }
        return result.toString();
    }

    // Helper class for test cases
    static class GraphTestCase {
        int n;
        int[][] edges;
        int source;

        GraphTestCase(int n, int[][] edges, int source) {
            this.n = n;
            this.edges = edges;
            this.source = source;
        }
    }

    // Main method to test Dijkstra’s algorithm
    public static void main(String[] args) {
        DijkstrasAlgorithm dijkstra = new DijkstrasAlgorithm();

        // Test cases
        List<GraphTestCase> testCases = new ArrayList<>();
        
        // Test case 1: Connected graph
        testCases.add(new GraphTestCase(
            4,
            new int[][]{{0,1,1}, {0,2,4}, {1,2,2}, {1,3,6}},
            0
        ));
        
        // Test case 2: Unreachable nodes
        testCases.add(new GraphTestCase(
            3,
            new int[][]{{0,1,2}},
            2
        ));
        
        // Test case 3: Single node
        testCases.add(new GraphTestCase(
            1,
            new int[][]{},
            0
        ));
        
        // Test case 4: Dense graph
        testCases.add(new GraphTestCase(
            4,
            new int[][]{{0,1,1}, {0,2,5}, {0,3,10}, {1,2,3}, {1,3,3}, {2,3,2}},
            0
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            GraphTestCase test = testCases.get(i);
            System.out.println("Test case " + (i + 1) + ": n=" + test.n + ", source=" + test.source);
            System.out.println("Edges: " + Arrays.deepToString(test.edges));
            String result = dijkstra.dijkstra(test.n, test.edges, test.source);
            System.out.println("Shortest distances: " + result + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: n=4, source=0
Edges: [[0, 1, 1], [0, 2, 4], [1, 2, 2], [1, 3, 6]]
Shortest distances: 0:0 1:1 2:3 3:7

Test case 2: n=3, source=2
Edges: [[0, 1, 2]]
Shortest distances: 0:INF 1:INF 2:0

Test case 3: n=1, source=0
Edges: []
Shortest distances: 0:0

Test case 4: n=4, source=0
Edges: [[0, 1, 1], [0, 2, 5], [0, 3, 10], [1, 2, 3], [1, 3, 3], [2, 3, 2]]
Shortest distances: 0:0 1:1 2:4 3:4

Explanation:

• Test case 1: From source 0, shortest paths: 0→1 (1), 0→1→2 (1+2=3), 0→1→3 (1+6=7).
• Test case 2: From source 2, no outgoing edges, so only 2 has distance 0; others are INF.
• Test case 3: Single node 0 has distance 0.
• Test case 4: From source 0, shortest paths: 0→1 (1), 0→1→2 (1+3=4), 0→1→3 (1+3=4).

How It Works

• NodeDistance: Stores a node and its tentative distance.
• MinPriorityQueue:
  • Uses a min-heap to prioritize nodes with smaller distances.
  • enqueue: Adds node-distance pair, sifts up.
  • dequeue: Removes smallest-distance node, sifts down.
• dijkstra:
  • Builds adjacency list from edges (directed).
  • Initializes distances to INF, source to 0.
  • Enqueues source with distance 0.
  • Processes nodes in order of increasing distance, updating neighbors’ distances if shorter.
  • Uses visited array to avoid reprocessing nodes.
  • Formats distances (INF for unreachable).
• Example Trace (Test case 1):
  • n=4, edges=[[0,1,1], [0,2,4], [1,2,2], [1,3,6]], source=0.
  • Adjacency list: [0: [(1,1),(2,4)], 1: [(2,2),(3,6)], 2: [], 3: []].
  • Initialize: distances=[0,INF,INF,INF], enqueue (0,0).
  • Dequeue (0,0): Update 1:1, 2:4, enqueue (1,1),(2,4).
  • Dequeue (1,1): Update 2:3 (1+2), 3:7 (1+6), enqueue (2,3),(3,7).
  • Dequeue (2,3): No updates.
  • Dequeue (3,7): No updates.
  • Result: "0:0 1:1 2:3 3:7".
• Main Method: Tests connected graph, unreachable nodes, single node, and dense graph.

Complexity Analysis Table

Note:

• V is the number of vertices, E is the number of edges.
• Time complexity: O(log V) for enqueue/dequeue; O((V + E) log V) for processing each node and edge with heap operations.
• Space complexity: O(V) for queue, distances, and visited array; O(E) for adjacency list.
• Worst case: O((V + E) log V) time, O(V + E) space for dense graphs.

✅ Tip: Use a min-heap priority queue in Dijkstra’s algorithm to efficiently select the node with the smallest tentative distance. Test with sparse and dense graphs to verify correctness.

⚠ Warning: Ensure edge weights are non-negative, as Dijkstra’s algorithm does not handle negative weights. Use a visited array to avoid reprocessing nodes in cyclic graphs.