G-33. Dijkstra's Algorithm - Using Set - Part 2

1. Context and Problem Statement

In the previous lecture, we implemented Dijkstra’s Algorithm using a Priority Queue (Min-Heap). While a priority queue efficiently retrieves the minimum distance node at the top, it has a distinct limitation: it cannot remove or modify stale, suboptimal path entries already inserted into the queue.

When multiple paths lead to the same node with varying weights, a priority queue simply pushes new, better distances on top while leaving older, higher distance entries lingering inside. This leads to redundant future iterations. To solve this inefficiency, we can utilize a Set data structure instead.

2. Core Mental Model: The Set Data Structure Advantage

A std::set in C++ (or equivalent self-balancing BST data structures) maintains two primary invariants:

1. Sorted Order: Elements are stored in ascending order, meaning the smallest element is always readily accessible at the top (st.begin()).
2. Dynamic Erasure: Unlike a priority queue where elements are immutable once inserted, a set permits direct logarithmic-time erasure (erase()) of existing elements.

Real-Life Analogy: Managing a Task List vs. Sticky Notes

Imagine you are managing project deadlines on a board.

• A Priority Queue is like a stack of sticky notes where you keep piling new estimates on top, even if an older, incorrect estimate for the same task is buried underneath. You eventually have to process those old estimates when you reach them.
• A Set is like a digital whiteboard sorted by urgency. If you discover a way to finish Task #5 in 8 days instead of your previously estimated 10 days, you don't just add a new note—you actively wipe out the old (10, Task #5) note and replace it cleanly with (8, Task #5).

3. How Set Dijkstra Differs from Priority Queue Dijkstra

The fundamental mechanics of Dijkstra's algorithm remain identical: greedily picking the node with the shortest known tentative distance and relaxing its adjacent edges. However, the update mechanism differs during edge relaxation.

4. Step-by-Step Dry Run Example

Let us trace how the set handles state updates when a shorter path is discovered.

1. Initial Setup:

   • Distance array initialized with 1e9 (infinity), except source node 0 set to 0.
   • Set initialized with (distance = 0, node = 0).

2. Reaching Node 5 with an Older Path:

   • Suppose at some point during the traversal, node 5 is reached with a suboptimal distance of 10, inserting (10, 5) into the set.
   • The distance array records dist[5] = 10.

3. Discovering a Superior Path:

   • Later, from node 4, we evaluate an alternative route to node 5 that costs 8.
   • Since the existing distance for node 5 is 10 (not 1e9), we recognize that someone has already reached node 5 before.
   • Because 8 < 10, this is a strictly better alternative.

4. The Erase-and-Replace Workflow:

   • Before inserting the new path, we search the set for the stale entry and remove it:
     C++

     Copy

     st.erase({10, 5}); // Erase old suboptimal path
     

   • We then insert the updated superior path:
     C++

     Copy

     st.insert({8, 5}); // Insert optimized path
     dist[5] = 8;
     

   • By erasing (10, 5), we prevent future redundant processing of the heavier weight path.

5. Complexity Analysis and Interview Insights

When asked by an interviewer whether a set is strictly superior to a priority_queue for Dijkstra's algorithm, the correct engineering response is nuanced:

• Time Complexity: Both algorithms operate in $O(E \log V)$ in the worst case.
• The Trade-off:
  • Using a set incurs an extra st.erase() logarithmic cost ($O(\log V)$) every time a shorter path is found, but it saves future iterations by pruning stale states.
  • Using a priority_queue avoids the overhead of explicit element erasure but processes redundant nodes that get popped and discarded.
• Verdict: In practice, their runtime performance is extremely close and depends heavily on graph density. Demonstrating this architectural trade-off to an interviewer shows exceptional depth of understanding.

6. Complete Implementation Code

Below are the production-grade implementations in C++ and Java, mirroring the exact logic discussed.

C++ Implementation

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

class Solution {
public:
    // Function to find the shortest distance of all the vertices 
    // from the source vertex S using a Set.
    vector<int> dijkstra(int V, vector<vector<int>> adj[], int S) {
        // Declare a set that stores pairs of {distance, node}
        // Set automatically keeps elements sorted by distance, then by node.
        set<pair<int, int>> st;

        // Distance array with large initial values (infinity)
        vector<int> dist(V, 1e9);

        // Initialize source node distance and insert into set
        dist[S] = 0;
        st.insert({0, S});

        while (!st.empty()) {
            // Retrieve the smallest element from the top of the set
            auto it = *(st.begin());
            int dis = it.first;
            int node = it.second;
            
            // Remove the processed element from the set
            st.erase(it);

            // Iterate through all adjacent nodes
            for (auto neighbor : adj[node]) {
                int adjNode = neighbor[0];
                int edgeWeight = neighbor[1];

                // Check if a shorter path is found
                if (dis + edgeWeight < dist[adjNode]) {
                    
                    // If the node was previously reached, erase its old entry from the set
                    if (dist[adjNode] != 1e9) {
                        st.erase({dist[adjNode], adjNode});
                    }

                    // Update distance and insert new optimized path into the set
                    dist[adjNode] = dis + edgeWeight;
                    st.insert({dist[adjNode], adjNode});
                }
            }
        }
        return dist;
    }
};

Java Implementation

import java.util.*;

class Pair {
    int distance;
    int node;

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

class Solution {
    // Function to find the shortest distance of all the vertices 
    // from the source vertex S using a TreeSet.
    static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S) {
        
        // TreeSet ordered by distance first, then by node to maintain uniqueness
        TreeSet<Pair> set = new TreeSet<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair p1, Pair p2) {
                if (p1.distance != p2.distance) {
                    return Integer.compare(p1.distance, p2.distance);
                }
                return Integer.compare(p1.node, p2.node);
            }
        });

        int[] dist = new int[V];
        Arrays.fill(dist, (int)(1e9));

        dist[S] = 0;
        set.add(new Pair(0, S));

        while (!set.isEmpty()) {
            Pair it = set.pollFirst(); // Retrieves and removes the smallest element
            int dis = it.distance;
            int node = it.node;

            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);

                if (dis + edgeWeight < dist[adjNode]) {
                    // Remove existing entry if node was already visited
                    if (dist[adjNode] != (int)(1e9)) {
                        set.remove(new Pair(dist[adjNode], adjNode));
                    }

                    dist[adjNode] = dis + edgeWeight;
                    set.add(new Pair(dist[adjNode], adjNode));
                }
            }
        }
        return dist;
    }
}

7. Summary and Key Takeaways

• Alternative to Priority Queue: Utilizing a set (or TreeSet) provides an alternative implementation for Dijkstra's Algorithm that maintains ascending order while allowing dynamic deletions.
• The Power of Erase: Unlike standard min-heaps which leave stale, higher-distance path entries intact, a set allows active removal of outdated paths via st.erase().
• Preventing Redundancy: Erasing suboptimal paths prevents future wasted iterations, keeping the search space clean and optimized.
• Logarithmic Overhead: Set insertions and deletions operate in $O(\log V)$ time, creating a balanced performance trade-off compared to priority queues.
• Code Simplicity: The structural flow remains identical to priority queue implementations, requiring only the addition of the .erase() check prior to updating the distance array.
• Interview Readiness: Explaining the nuanced difference in state elimination between Priority Queues and Sets demonstrates elite technical communication and deep algorithmic comprehension.