Module 98

Here is the clean, standard, and most commonly asked pseudocode for Dijkstra’s Algorithm (Single-Source Shortest Path in graphs with non-negative weights).

DIJKSTRA’S ALGORITHM – Using Priority Queue (Min-Heap)

DIJKSTRA(G, source)
    // G is graph with adjacency list: G[u] = list of (v, weight)
    for each vertex v in G
        dist[v] ← ∞
        parent[v] ← NULL
        visited[v] ← FALSE
    
    dist[source] ← 0
    
    // Min-priority queue (extract smallest distance first)
    Let PQ be a min-priority queue (key = dist)
    INSERT(PQ, (source, 0))          // (vertex, distance)

    while PQ is not empty
        u ← EXTRACT-MIN(PQ)          // vertex with smallest dist
        if visited[u] == TRUE
            continue                 // skip outdated entries (optional optimization)
        
        visited[u] ← TRUE            // mark as processed

        for each neighbor v of u in G[u]
            weight ← weight of edge (u, v)
            if visited[v] == FALSE and dist[u] + weight < dist[v]
                dist[v] ← dist[u] + weight
                parent[v] ← u
                INSERT(PQ, (v, dist[v]))   // or DECREASE-KEY if supported
                // In simple implementations, we just insert duplicate entries

Notes for Interviews/Exams:

• In practice (especially in code), we allow multiple entries for same vertex in the priority queue — older (worse) ones are ignored when extracted (using the visited check).
• This version works perfectly with standard binary heap.

Correct & Simpler Version (Most Used in Competitive Coding & Exams)

DIJKSTRA(G, source)
    Initialize dist[source] = 0, dist[others] = ∞
    Let PQ be a min-priority queue
    PQ.insert(source, 0)

    while PQ is not empty
        u ← PQ.extractMin()                 // get node with smallest distance
        for each neighbor v of u
            if dist[u] + weight(u,v) < dist[v]
                dist[v] ← dist[u] + weight(u,v)
                parent[v] ← u
                PQ.insert(v, dist[v])       // allow duplicates

This version is widely accepted even though it may have O(V²) entries in worst case — but it's easy to remember and implement.

Example Execution

Graph:

0 → 1 (4), 0 → 2 (1)
1 → 3 (1)
2 → 1 (2), 2 → 3 (5)
3 → (destination)

Source = 0
Final distances:
dist[0]=0, dist[1]=3, dist[2]=1, dist[3]=4
Path to 3: 0 → 2 → 1 → 3

Time Complexity

Priority Queue Type	Time Complexity	Space Complexity
Binary Heap (with duplicates)	O((V + E) log V)	O(V)
Fibonacci Heap	O(E + V log V)	O(V)

Important Points for Exams

• Works only when all edge weights ≥ 0
• Greedy algorithm
• Finds shortest path from one source to all vertices
• Cannot handle negative weights → use Bellman-Ford instead

You can now confidently write and explain Dijkstra’s pseudocode in any exam or interview!