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

[oaktree]

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:

1. Adjacency Matrix
2. 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 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 ith 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 ifs 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.