Graphs & Network Topologies

You have hit on one of the most critical differences between competitive programming hacks and real-world systems engineering.

In standard textbook Dijkstra, because std::priority_queue does not support a native decrease_key() operation, engineers take the lazy route: they just push duplicate entries into the heap and skip stale ones with if (d > dist[u]) continue;. This is called Lazy Deletion Dijkstra.

While lazy Dijkstra works fine on small graphs, on dense graphs with 10 million edges, your heap stores up to 10 million items instead of 1 million nodes, blowing through your CPU’s L3 cache.

The Solution: Indexed Priority Queue

An Indexed Binary Heap (Indexed Priority Queue) maintains an internal inverse lookup array (pos[u]) that tracks the exact heap index of every node u.

When a shorter path to node u is discovered:

1. If u is already in the heap, you don’t insert a duplicate—you call decrease_key(u, new_dist), which directly updates the value in-place and sifts it up in O(log V) time!
2. The heap size never exceeds V (the number of vertices).

High-Performance C++20 Indexed Min-Heap Dijkstra

#include <vector>
#include <cstdint>
#include <algorithm>

struct Edge {
    int to;
    int weight;
};

class IndexedMinHeap {
    std::vector<int> heap;      // Node IDs
    std::vector<int> pos;       // pos[node] = index in heap array
    std::vector<int64_t>& dist; // Reference to external distance array

    void swapNodes(int i, int j) {
        std::swap(heap[i], heap[j]);
        pos[heap[i]] = i;
        pos[heap[j]] = j;
    }

    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (dist[heap[i]] < dist[heap[parent]]) {
                swapNodes(i, parent);
                i = parent;
            } else break;
        }
    }

    void siftDown(int i) {
        int n = heap.size();
        while (2 * i + 1 < n) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int smallest = left;
            if (right < n && dist[heap[right]] < dist[heap[left]]) {
                smallest = right;
            }
            if (dist[heap[smallest]] < dist[heap[i]]) {
                swapNodes(i, smallest);
                i = smallest;
            } else break;
        }
    }

public:
    IndexedMinHeap(int max_nodes, std::vector<int64_t>& d) 
        : pos(max_nodes, -1), dist(d) {}

    bool empty() const { return heap.empty(); }

    void pushOrDecreaseKey(int node, int64_t new_dist) {
        dist[node] = new_dist;
        if (pos[node] == -1) {
            pos[node] = heap.size();
            heap.push_back(node);
            siftUp(pos[node]);
        } else {
            siftUp(pos[node]);
        }
    }

    int extractMin() {
        int root = heap[0];
        swapNodes(0, heap.size() - 1);
        pos[root] = -1;
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
        return root;
    }
};

std::vector<int64_t> dijkstraIndexed(int n, int src, const std::vector<std::vector<Edge>>& adj) {
    const int64_t INF = 1e18;
    std::vector<int64_t> dist(n, INF);
    IndexedMinHeap pq(n, dist);

    pq.pushOrDecreaseKey(src, 0);

    while (!pq.empty()) {
        int u = pq.extractMin();
        for (const auto& edge : adj[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                pq.pushOrDecreaseKey(edge.to, dist[u] + edge.weight);
            }
        }
    }
    return dist;
}

Performance Benchmark Comparison

By enforcing an explicit upper bound of V elements in the heap, the entire indexed heap fits cleanly inside modern CPU L2/L3 caches, drastically accelerating routing throughput!