C++UCS301
Graphs & ApplicationsC++17

Dijkstra’s Algorithm

Dijkstra finalises minimum distances from one source by repeatedly extracting the closest unsettled vertex.

What to understand

  • Relaxation
  • Min-priority queue
  • Stale queue entries
  • Non-negative edge requirement

Remember this

  1. 1Never use Dijkstra with negative edges
  2. 2Relax when a shorter route is found
  3. 3Heap implementation is O((V+E)log V)

Detailed notes

Dijkstra maintains tentative source distances. Extracting the smallest tentative distance is safe with non-negative edges: any alternative route through unsettled vertices can only add non-negative cost and cannot improve that minimum later.

C++ priority_queue lacks decrease-key, so a common implementation pushes a new pair after every improvement. When an older pair is popped, comparing it with the current distance identifies it as stale.

How it works

  1. 1Initialise source to zero and all others to infinity.
  2. 2Extract the smallest current distance.
  3. 3Skip stale entries.
  4. 4Relax every outgoing edge and record parent on improvement.

Worked trace

Relax from the closest vertex

A→B=4, A→C=1, C→B=2
  1. 1Initial distances: A=0, B=∞, C=∞.
  2. 2From A: B becomes 4 and C becomes 1.
  3. 3Extract C because 1 is smallest; route A→C→B costs 3.
  4. 4Update B from 4 to 3; later stale entry (4,B) is ignored.
Result: Shortest A→B distance is 3, not direct edge cost 4

Where it is used

  • Road and network routing with non-negative costs
  • Service-area and nearest-facility computation
  • Subroutine in many optimisation systems

Common mistakes

  • Using negative edge weights
  • Adding a weight to an infinity sentinel and overflowing
  • Marking a vertex final before confirming the popped distance is current

Complexity analysis

OperationBestAverageWorstExtra space
Shortest pathsO((V+E) log V)O((V+E) log V)O((V+E) log V)O(V+E)

C++ implementation

C++17 reference
main.cpp

Dijkstra with a min-priority queue

Stale queue entries are skipped instead of trying to decrease a key already inside std::priority_queue.

vector<long long> dijkstra(
    const vector<vector<pair<int, int>>>& graph, int source) {
    const long long INF = 1e18;
    vector<long long> distance(graph.size(), INF);
    using State = pair<long long, int>;
    priority_queue<State, vector<State>, greater<State>> pending;
    distance[source] = 0;
    pending.push({0, source});

    while (!pending.empty()) {
        auto [currentDistance, current] = pending.top(); pending.pop();
        if (currentDistance != distance[current]) continue;
        for (auto [next, weight] : graph[current]) {
            long long candidate = currentDistance + weight;
            if (candidate < distance[next]) {
                distance[next] = candidate;
                pending.push({candidate, next});
            }
        }
    }
    return distance;
}
22 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.