Graph Theory37 sections · 1633 units
Open in Course

Dijkstra's Algorithm - The Loop

Processing nodes in order

By default, C++ priority_queue puts the largest element at top (max-heap). You want the smallest (min-heap).

Trick: store negative distances. Or use greater<pair<int,int>> as comparator:

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq

This creates a min-heap of (distance, node) pairs. The pair with smallest distance comes out first. Alternatively, push (-distance, node) and negate when you pop.