Implementing Dijkstra

Problem Definition

Link : Implementing Dijkstra

You are given a graph represented using an adjacency matrix or adjacency list, and a source vertex S. Find the shortest path from the source to all vertices using Dijkstra’s Algorithm.

Intuition Behind Dijkstra's Algorithm

Dijkstra’s algorithm is a greedy shortest path algorithm designed for non-negative weight graphs. It maintains a set of nodes whose minimum distance from the source is already known and iteratively selects the closest unvisited node to explore.

Core Idea:

At every step, pick the node with the minimum known distance and expand it, because no other unexplored path can improve it (greedy selection).

Why Not Use BFS?

BFS only works for unweighted graphs or unit weights. In weighted graphs:

• BFS may visit a far vertex first due to being at the same "level" in a queue.

• But a smaller weight path might exist and be missed.

So, BFS doesn’t account for the weight of edges—this is where Dijkstra is necessary.

Data Structure Choices

Using PriorityQueue (Java Min-Heap)

• Always gives you the node with the least current distance efficiently.

• Ensures optimal performance by processing shortest paths first.

PriorityQueue<Pair> pq = new PriorityQueue<>((a,b) -> a.dist - b.dist);

Using Set (C++ std::set or TreeSet Equivalent)

• Set supports fast removal and re-insertion.

• But Java’s TreeSet doesn’t allow duplicate keys, which is a major issue in Dijkstra where multiple nodes can have the same tentative distance.

• Therefore, TreeSet is avoided in Java unless manually handled with composite keys.

Alternative: Use PriorityQueue with a distance array to skip outdated entries.

Why Not Use Simple Queue?

• A normal queue doesn’t prioritize the minimum distance.

• Higher-cost paths may be processed first, violating the optimal greedy approach.

Algorithm Steps (Adjacency List Version)

1. Initialize a distance array dist[] of size V with Integer.MAX_VALUE.

2. Set dist[src] = 0.

3. Create a min-heap (PriorityQueue) storing (distance, node).

4. While the queue is not empty:

   • Pop the node with the smallest distance.

   • For each neighbor:

     • If dist[curr] + weight < dist[adj], update it and push into the heap.

Java Code (Using PriorityQueue)

class Solution {
    static class Pair {
        int node, dist;
        Pair(int node, int dist) {
            this.node = node;
            this.dist = dist;
        }
    }

    static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        pq.add(new Pair(S, 0));

        while (!pq.isEmpty()) {
            Pair curr = pq.poll();
            int u = curr.node;
            int d = curr.dist;

            for (ArrayList<Integer> neighbor : adj.get(u)) {
                int v = neighbor.get(0);
                int weight = neighbor.get(1);

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Pair(v, dist[v]));
                }
            }
        }

        return dist;
    }
}

Dry Run

Input:

V = 4
Edges:
0 → 1 (1)
0 → 2 (4)
1 → 2 (2)
1 → 3 (6)
2 → 3 (3)

Start from S = 0:

• Step 1: dist[0] = 0

• Step 2: Visit 0 → 1 (dist[1] = 1), → 2 (dist[2] = 4)

• Step 3: Visit 1 → 2 (1 + 2 = 3) → update dist[2] = 3, → 3 (1 + 6 = 7)

• Step 4: Visit 2 → 3 (3 + 3 = 6) → update dist[3] = 6

Final distances: [0, 1, 3, 6]

Time and Space Complexity

Let:

• V = number of vertices

• E = number of edges

Using PriorityQueue (Min Heap):

• Each node is pushed/popped at most once → O(V log V)

• Each edge can be relaxed → O(E log V) (pushing neighbors into the heap)

• Total time complexity:

  T.C. = O((V + E) log V)
  

Why E Can Be Up to V²?

• In a dense graph, every vertex can have an edge to every other vertex.

• So maximum E = V * (V - 1) ≈ V²

• Worst-case time complexity becomes: O(V² log V)

Applications

• Shortest paths in non-negative weighted graphs

• GPS navigation systems

• Routing protocols in computer networks

• Game development (pathfinding algorithms)

• Emergency response systems

Why TreeSet Fails in Java

Java's TreeSet:

• Does not allow duplicate keys

• This means if two nodes have the same tentative distance, only one will remain in the set

Result: You could accidentally skip a node that’s critical for reaching the shortest path.

Better Practice:

• Use PriorityQueue even if it means occasionally inserting outdated entries.

• Use the dist[] array to skip over nodes that no longer match the current shortest distance when polled from the heap.