 Graph Algorithms (Part 1.1): Dijkstra's Shortest Path [Code v1]

(oaktree) #1

Hey 0x00sec people! Not long ago, I said I would put up some source code for Dijkstra’s Algorithm. Today, I’ll be showing you just one way to do it. We’ll be utilizing an Adjacency Matrix, which is simply a 2D Array. As we progress, each implementation will be more efficient than the last.

Taking a page from @dtm’s book, this post is best understood when the reader has:

``````Intermediate C++ Skills
``````

Representation of A Graph

The first step in implementing any algorithm is understanding how to represent relevant data in a computer. So, how would we represent a graph in memory?

There are really just two ways:

Today, we’re going to use the first one. Take a look at the image below: On the left, what is shown is a graph much like the one from the first part of this series. To the right of that graph is its corresponding representation in an adjacency matrix.

This particular adjacency matrix is a Boolean one: a `1` means that an edge connects the two nodes. A matrix’s values can also be used to keep track of distances.

Note: A matrix is represented in computer as a 2D array. The outer array makes up the rows; the inner the columns. Generally: `some_matrix[row][col]`.

Let’s Start Coding

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

int dijkstra(std::vector< std::vector<int> >& matrix, int start, int end) {

std::vector<int> distances(matrix.size()), previous(matrix.size());
std::vector<int> nodes, path;

// ...
``````

We include our headers and then declare the function `dijkstra`. This function takes, as parameters, an adjacency matrix represented by a 2D `std::vector`, a starting point, and an ending point. The start/end points are assumed to be from a zero-based index.

Then, we declare a few more vectors.

• `distances` will keep track of the distance between each node and the `start` node.
• `previous` keeps track of the order of visitation of the nodes.
• `nodes` is a `std::vector<int>` containing all of the nodes.
• `path` is simply the path to take from `start` to `end`. It’s empty because we have yet to find the path.
``````       // ...

for (int i = 0, n = matrix[start].size(); i < n; i++) {

if (i == start)
distances[i] = 0;
else
distances[i] = std::numeric_limits<int>::max();

nodes.push_back(i);
}

// ...
``````

We now go through each node, and set the distance to “infinity,” represented by the maximum value of an integer (`numeric_limits<int>::max()`). But, if the `i`th node is our `start` node, we set the distance to `0`. We then `push_back` each node.

``````        // ...
auto comp = [&](int l, int r) {return distances[l] > distances[r];};
std::sort(nodes.begin(), nodes.end(), comp);

// ...
``````

Okay, that first line there seems a little daunting. Basically, we create a custom comparator, so that we can sort `nodes` by the distance between each node and `start`, with the smallest distances at the end, or back, of `nodes`.

``````        // ...
while(!nodes.empty()) {
int smallest = nodes.back();
nodes.pop_back();

if (smallest == end) {

while(smallest != start) {

path.push_back(smallest);
smallest = previous[smallest];
}

path.push_back(start);
std::reverse(path.begin(), path.end());
break;
}

if (distances[smallest] == std::numeric_limits<int>::max())
break;

for(int i = 0, n = matrix[smallest].size(); i < n; i++) {
int tmp = distances[smallest] + matrix[smallest][i];

if (tmp < 0)
tmp = std::numeric_limits<int>::max();
// combat integer overflow!

if (tmp < distances[i]) {
distances[i] = tmp;
previous[i] = smallest;

std::sort(nodes.begin(), nodes.end(), comp);
}
}
}
// ...
``````

Now we enter a `while` loop, which says, “while we still have nodes…” The first thing we’re going to do is take the smallest node in `nodes` and “visit” it by popping it off of `nodes` and storing it in `smallest`.

Skip those first two `if`s and go to that `for` loop. This loop says, “for each node connected to `smallest`, do…”

In the loop, we first make a variable `tmp` equal to the sum of `distances[smallest]` and `matrix[smallest][i]`. This means, `tmp` is equal to the distance from `start` to `smallest` plus the distance from `smallest` to node `i`. `tmp` is, therefore, a possible distance from `start` to node `i`. But, we only want to use this distance if it’s less than the one we already may have.

First, let’s make sure we didn’t add `numeric_limits<int>::max()` to some number above zero and accidentally overflow `tmp` to the negatives. We correct `tmp` to `numeric_limits<int>::max()` if we did overflow it.

Now we’re at the second `if` in the `for` loop. If `tmp` is smaller than `distances[i]`, it means that we have found a better route from `start` to `i`. So, we update the distance and record that the node we visit before `i` should be `smallest`. Since we have updated a distance, we also need to re`sort` `nodes`.

Okay, let’s go back to the first `if` in the `while` loop. If/when we reach the end, the code inside this `if` runs. We build up the `path` by calling on previous, and then recursively defining `smallest` as the `smallest` that came before it. Then, we `push_back( start )` to complete the path. We have to `reverse` it first, though, since the first element in `path` is `end` and the last is `start`.

The second `if` in the `while` loop handles the corner case of not being able to reach `end` from `start`. If the smallest distance is `numeric_limits<int>::max()`, our “infinity”, then `end` can never be reached.

``````        // ...
for(auto& v : path) std::cout << v << " ";
std::cout << "\n";

return distances[end];
} // end of dijkstra()
``````

In this final snippet of `dijkstra`, we print out the `path` and then `return distances[end]`, the distance from `start` to `end`.

I’ll leave the `main()` function up to you guys, but here is the source for this post. Note: I have slightly modified the code shown here for simplicity and/or the tutorial’s sake. There is a main function in that, but feel free to make your own, as long as it satisfies the adjacency matrix.

Conclusion

That’s all for today. Next time, I’ll be rolling out a (much) more optimized version of the algorithm that takes advantage of adjacency lists and more concise coding techniques I have omitted from this for clarity reasons.

4 Likes

Graph Algorithms (Part 2.0): The Bellman-Ford Algorithm [Concept]
Graph Algorithms (Part 2.1): Bellman-Ford [Implementation]
(oaktree) closed #2

This topic was automatically closed after 30 days. New replies are no longer allowed.

0 Likes