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
read the first article
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:
 Adjacency Matrix
 Adjacency List
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 zerobased index.
Then, we declare a few more vectors.

distances
will keep track of the distance between each node and thestart
node. 
previous
keeps track of the order of visitation of the nodes. 
nodes
is astd::vector<int>
containing all of the nodes. 
path
is simply the path to take fromstart
toend
. 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 resort
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.