Dijkstra's Algorithm - Using Priority Queue - C++ and Java - Part 1

Dijkstra's Algorithm is one of the most fundamental and crucial algorithms in computer science for solving Single-Source Shortest Path problems on weighted graphs with non-negative edge weights. This guide covers its core mechanics, step-by-step trace, implementation details in C++ and Java, and why it fails in graphs with negative weight cycles.

1. Why Do We Need Dijkstra's Algorithm? (Problem Statement)

• The Core Objective: Given a weighted graph and a designated Source Node, find the minimum (shortest) path distance from the source node to every other node in the graph.
• The Status Quo Challenge: In an unweighted graph, Breadth-First Search (BFS) naturally finds the shortest path because each step costs an equal increment of 1. However, in a weighted graph, different edges carry different costs (weights). Traveling direct may look appealing, but taking a detour through multiple cheaper edges can result in a smaller total distance.
• Example Scenario:
  Structure & Concept Flow

  Copy DiagramCopy

  Source Node = 0

  Path A (Direct 0 -> 1): Weight = 4

  Path B (0 -> 2 -> 1): Weight = 4 + 2 = 6

  Path C (Alternative route): Weight = 1 + 2 = 3 (Shortest!)

   
  We need a systematic method to evaluate all valid pathways and guarantee that we record the absolute minimum cost to reach each node.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Imagine navigating a city road network where every road has a toll or distance cost. You start at your home (Source Node 0) with a map and a notebook. You explore neighboring junctions step by step, always greedily picking the currently cheapest known route to inspect next. As you discover shorter shortcuts to various intersections, you update your notebook, discarding longer, redundant routes.

• Greedy Choice Property: At any point, Dijkstra's algorithm greedily extracts the node with the current minimum accumulated distance from the priority queue, ensuring that once a node is finalized, its shortest path cannot be beaten.

3. Data Structures & Initial Configuration

To implement Dijkstra's Algorithm efficiently using a Priority Queue (Min-Heap), three main data structures are required:

1. Adjacency List: Stores the graph where each node maps to a list of adjacent pairs (neighbor_node, edge_weight).
   Structure & Concept Flow

   Copy DiagramCopy

   Adjacency List Structure:

   Node 0 -> [(1, 4), (2, 4)]

   Node 4 -> [(2, 1), (5, 3)]

    
2. Min-Heap (Priority Queue): Always keeps the pair with the smallest distance at the top. It stores elements in (distance, node) format.
3. Distance Array: A 1D array initialized with a very large integer (1e9 or infinity) representing the shortest distance from the source to every node. Unreached nodes remain at infinity.

4. Step-by-Step Execution Flow Walkthrough

Let's walk through the exact mechanics of how the algorithm processes nodes:

1. Initialization:

   • Set distance[source] = 0.
   • Push (0, source) into the Min-Heap priority queue.
   • Initialize all other nodes in the distance array to infinity.

2. Iteration (BFS-style traversal):

   • Pop the top element from the Min-Heap (let's say (dist, node)).
   • Iterate through all adjacent neighbors of the current node using the adjacency list.
   • Calculate the new tentative distance: new_dist = dist + edge_weight.
   • Relaxation Step: If new_dist < distance[neighbor]:
     • Update distance[neighbor] = new_dist.
     • Push (new_dist, neighbor) into the Priority Queue.

5. Complete Implementation: C++ vs. Java

C++ Implementation (Using std::priority_queue)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> dijkstra(int V, vector<vector<int>> adj[], int S) {
        // Min-heap: stores pairs of {distance, node}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        // Distance array with a large value representing infinity
        vector<int> dist(V, 1e9);
        
        // Initial configuration for source node
        dist[S] = 0;
        pq.push({0, S});
        
        while(!pq.empty()) {
            int dis = pq.top().first;
            int node = pq.top().second;
            pq.pop();
            
            // Traverse adjacent nodes
            for(auto it : adj[node]) {
                int adjNode = it[0];
                int edgeWeight = it[1];
                
                // Relaxation step: if a shorter path is found
                if(dis + edgeWeight < dist[adjNode]) {
                    dist[adjNode] = dis + edgeWeight;
                    pq.push({dist[adjNode], adjNode});
                }
            }
        }
        return dist;
    }
};

Java Implementation Equivalent

import java.util.*;

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

    // Function to find the shortest distance of all the vertices from the source vertex S.
    static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S) {
        // Min-heap based on distance
        PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> x.distance - y.distance);
        
        int[] dist = new int[V];
        Arrays.fill(dist, (int)(1e9));
        
        dist[S] = 0;
        pq.add(new Pair(0, S));
        
        while(!pq.isEmpty()) {
            int dis = pq.peek().distance;
            int node = pq.peek().node;
            pq.poll();
            
            for(int i = 0; i < adj.get(node).size(); i++) {
                int adjNode = adj.get(node).get(i).get(0);
                int edgeWeight = adj.get(node).get(i).get(1);
                
                // Relaxation step
                if(dis + edgeWeight < dist[adjNode]) {
                    dist[adjNode] = dis + edgeWeight;
                    pq.add(new Pair(dist[adjNode], adjNode));
                }
            }
        }
        return dist;
    }
}

6. Why Dijkstra's Algorithm Fails with Negative Weights

• The Negative Weight Paradox: Dijkstra's algorithm relies on the assumption that adding an edge to a path can never decrease the total path distance (monotonicity of non-negative weights).
• Infinite Loop / Incorrect Shortest Paths: If a graph contains a negative edge weight or a negative weight cycle, traversing the cycle continually reduces the total cost.
  • Example: Going from Node 0 to Node 1 costs -2. Returning from Node 1 to Node 0 costs another -2. Total cost keeps dropping infinitely (0 -> -2 -> -4 -> -6 ...).
• Conclusion: Dijkstra's algorithm is strictly applicable only to graphs with non-negative edge weights. For graphs with negative weights, algorithms like Bellman-Ford or Floyd-Warshall must be used.

7. Time Complexity Analysis

• Priority Queue Operations: Each edge is relaxed at most once. Pushing and popping from the Priority Queue takes logarithmic time relative to the number of elements in the queue.
• Overall Time Complexity: $O(E \log V)$
  • Where $E$ is the total number of edges in the graph.
  • Where $V$ is the total number of vertices (nodes) in the graph.

8. Summary and Key Takeaways

• Core Purpose: Computes the single-source shortest path to all vertices in a weighted graph.
• Data Structures: Utilizes an Adjacency List, a Min-Heap (Priority Queue) storing (distance, node) pairs, and a Distance Array initialized to infinity.
• Greedy Extraction: Always processes the node with the minimum accumulated distance first.
• Relaxation Condition: If current_distance + edge_weight < recorded_distance, update the distance array and push the new state into the priority queue.
• Constraint: Fails completely on graphs containing negative edge weights or negative cycles due to infinite distance reduction loops.
• Efficiency: Achieves an optimal time complexity of $O(E \log V)$ using a Priority Queue.