Dijkstra algorithm implementation with adjacency list

Question

I've implemented the Dijkstra Algorithm to obtain the minimum paths between a source node and every other.

#include <bits/stdc++.h>

typedef std::vector<std::list<int>> AdjacencyList;
typedef std::vector<std::vector<int>> Weights;

std::vector<int> dijkstra(AdjacencyList &adj, Weights weights, int src) {
    int n = adj.size();

    std::vector<int> prev(n, -1);
    std::vector<int> dist (n, INT_MAX);
    std::vector<bool> visited(n, false);

    auto comp = [&dist](const int& lhs, const int& rhs) -> bool { return dist[lhs] > dist[rhs]; };
    std::priority_queue<int, std::vector<int>, decltype(comp)> candidates(comp);

    candidates.push(src);
    dist[src] = 0;
    for (int j = 0; j < n - 1; ++j) {
        int next = candidates.top();
        candidates.pop();
        visited[next] = true;
        for(std::list<int>::const_iterator it = adj[next].begin(); it != adj[next].end(); it++) {
            int neighbor = *it;
            if (!visited[neighbor] && (dist[next] + weights[next][neighbor] < dist[neighbor])) {
                dist[neighbor] = dist[next] + weights[next][neighbor];
                prev[neighbor] = next;
                candidates.push(neighbor);
            }
        }
    }
    return prev;
}

I wrote this code to practice but also to be used at competition contests. So, i want this to be simple, clear and efficient at the same time (without losing so much readability). Any advices?

Answer 1

Advice 1

int n = adj.size();

I would change int to size_t, since it counts size that may not be negative.

Advice 2

for (int j = 0; j < n - 1; ++j) {
    ...
}

I would change it to

while (!candidates.empty()) {

}

This omits some unnecessary computation in case the graph is disconnected.

Advice 3

candidates may be renamed to open, open_list or frontier; that is more or less conventional naming for that data structure in pathfinding community.

Advice 4

I would change typedef std::vector<std::vector<int>> Weights; to typedef std::unordered_map<int, std::unordered_map<int, size_t>> Weights;. This makes filling the edge weights much more easier; especially on sparse graphs:

w[a][b1] = 3;
w[a][b2] = 1;
...

Advice 5

if (!visited[neighbor] && (dist[next] + weights[next][neighbor] < dist[neighbor])) {
    ...
}

This condition is a bug. It should be

if (dist[neighbor] == INT_MAX || (dist[next] + weights[next][neighbor] < dist[neighbor])) {
    ...
}

(Note dist[neighbor] == INT_MAX and || instead of &&. You can try changing || to && and see its effect here.)

Answer 2

Optimization

Your dijkstra implementation can potentially push the same vertex onto the priority queue more than once. This happens when you encounter a vertex for the second time, but this time its distance is less than its previous distance. Because of this, you may find yourself pulling the same vertex off the priority queue multiple times. You should add the following check in the outer loop:

candidates.pop();
if (visited[next])
    continue;

otherwise your algorithm may run far slower than it should.

Bug

I didn't notice this before, but your loop termination condition is wrong. You are looping exactly n-1 times under the assumption that each loop adds a vertex to the path. However, due to the duplicate vertex possibility mentioned above, you may not make progress on each loop iteration. You should modify the loop to terminate when the priority queue becomes empty. Alternatively, you can keep a count of the number of visited vertices and terminate when you reach n.