Dijkstra’s Algorithm (C++)

Table of contents

1. Things to Remember
2. Adjacency List
3. Minimum Priority Queue
4. Initialization
   1. Distance and Predecessor Vectors
   2. Source Initialization
5. The Loop

---

Things to Remember

• Dijkstra’s algorithm is a greedy algorithm.
• It finds the shortest path from a source vertex to all other vertices.
• The graph must not have negative edge weights.
• We need to build an adjacency list to represent the graph.
• We use a minimum priority queue.

---

Adjacency List

The adjacency list adj needs to be built with given inputs:

using Dist = int;
using Node = int;
using EdgeTo = pair<Dist, Node>;  // Do not confuse this with the PqElem later

vector<vector<EdgeTo>> adj(n + 1);  // If vertices are 1-indexed
// Build the adjacency list with loop
  adj[u].push_back({w, v});  // Edge from u to v with weight w

---

Minimum Priority Queue

The elements of the priority queue are pairs of:

• Total distance from the source vertex to this vertex
• The to-vertex

using AccD = int;
using Node = int;
using PqElem = pair<AccD, Node>;

The thing about priority queues in C++ is that they are max-heap by default. We need to reverse the comparison to make it a min-heap.

If you’re using pair as the element type, you can simply use the following:

priority_queue<PqElem, vector<PqElem>, greater<PqElem>> pq;

If you’re using some other struct or class, you could overload the operator>:

struct PqElem {
  AccD dist;
  Node v;

  bool operator>(const PqElem& other) const {
    return dist > other.dist;
  }
};
priority_queue<PqElem, vector<PqElem>, greater<PqElem>> pq;

Or use a lambda function:

auto cmp = [](const PqElem& a, const PqElem& b) {
  return a.dist > b.dist;
};

priority_queue<PqElem, vector<PqElem>, decltype(cmp)> pq(cmp);

Another thing about priority queues in C++ is that we cannot update the priority of an element.

---

Initialization

Distance and Predecessor Vectors

We will keep track of the current shortest distance and current predecessor of each vertex.

vector<AccD> cur_dist(n + 1, INT_MAX);
vector<Node> pred(n + 1, -1);

Source Initialization

Let’s say we are starting from vertex s.

First, we know the shortest distance to s from s is 0.

cur_dist[s] = 0;

Obviously, predecessor of the source vertex remains -1.

Then, we push the source vertex to the priority queue.

By the way, pushing an element {dist_to_u, u} has the following meaning:

• Okay, so far, the shortest distance to u is dist_to_u.
• Use this information later to update distances to vertices connected to u.

// PqElem: {acc_dist, vertex}
pq.emplace(0, s);

Isn't `cur_dist` and `acc_dist` redundant?

You maybe asking why we have two variables to store the same information.

As mentioned above, this is because we cannot update the priority of an element in the priority queue.

While we will still be popping elements from the priority queue, we are going to be storing the best distance to each vertex in cur_dist.

The stale distances in the priority queue will be ignored based on its comparison with the cur_dist.

---

The Loop

Once the formulation above is set up, this is probably the most intuitive part of the algorithm.

while (!pq.empty) {
  PqElem elem = pq.top();
  pq.pop();

  int dist_to_u = elem.first;
  int u = elem.second;

  // If the distance is stale, ignore
  if (dist_to_u > cur_dist[u]) continue;

  for (const EdgeTo& edge : adj[u]) {
    int w = edge.first;
    int v = edge.second;

    // Relaxation
    if (cur_dist[v] > cur_dist[u] + w) {
      cur_dist[v] = cur_dist[u] + w;
      pred[v] = u;
      pq.emplace(cur_dist[v], v);
    }
  }
}