5
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ @jscherman You are welcome. \$\endgroup\$ – coderodde Jul 26 '17 at 5:09
  • 1
    \$\begingroup\$ Sorry for asking this so late, i've been busy. On the advice 5 you proposed adding dist[neighbor] == INT_MAX to the guard but i don't understand why. Wouldn't that be covered with the other condition? I mean, dist[next] + weights[next][neighbor] will always be less than dist[neighbor] if the latter is INT_MAX so it will be true either ways. On the other hand, why is the !visited[neighbor] wrong? I understand that would be redundant if i add the condition proposed by @JS1 but i don't understand why is wrong otherwise. \$\endgroup\$ – jscherman Jul 27 '17 at 1:55
  • \$\begingroup\$ @jscherman On the second thought, we do not need dist[neighbor] == INT_MAX, but that is due to only the fact that you set each dist[neighbor] to that value. If instead we set those dist values only when we reach them, we would have to have a mechanism that tells us that the neighbor wasn't reached yet. \$\endgroup\$ – coderodde Jul 27 '17 at 17:05
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You don't need this if statement since it will be handled by dist[next] + weights[next][neighbor] < dist[neighbor] (the dist of visited nodes cannot be improved). \$\endgroup\$ – coderodde Jul 25 '17 at 7:35
  • \$\begingroup\$ @coderodde Yes but in the mean time you will have wasted \$O(n)\$ time iterating through that vertex's edges for no reason. Overall, instead of \$O(E + V \log V)\$, it could become as bad as \$O(V^3 \log V)\$ in the worst case. \$\endgroup\$ – JS1 Jul 25 '17 at 9:23
  • \$\begingroup\$ Oops! You meant to add that test to the outermost loop? My bad. However, note that \$O(E + V \log V)\$ is achievable only with Fibonacci heaps. \$\endgroup\$ – coderodde Jul 25 '17 at 10:39
  • \$\begingroup\$ @coderodde I edited that section to be more clear on where to put the check. You're right about the complexity - with the heap and the check it would be \$O(V^2 \log V)\$ in the worst case, not \$O(E + V \log V)\$. But without the check it would still be \$O(V^3 \log V)\$. \$\endgroup\$ – JS1 Jul 25 '17 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.