Who doesn’t like graph theory? Come on… it is the foundation of all living beings! Ok maybe not but it is still a bit interesting from a theoretical standpoint. Graph theory is the study of graphs and their relationships between points on that graph and their overall collection. It is often made up of vertexes (aka nodes) and the connections between them known as edges. Linked together they form a spider web and using Dijkstra’s algorithm we can find the shortest distance between our start node and the end node. I will show you how using C++ on this entry of the Programmer’s Underground!
So how does it all work? Graph theory can get pretty complicated and studying the relationship between nodes using their edges isn’t exactly something we dream about. Unless you are part of DIC staff and addicted to programming theory. Hopefully I can put that nightmare to rest with a little explanation of Dijkstra’s Algorithm and how it works for finding the path with the “least cost” between two nodes of a graph.
But first I want to show you a classic example of a graph we are talking about here and what Dijkstra’s Algorithm was designed to do.
The above graph I got from Wikipedia. It is a very simple graph but it will illustrate our point nicely. Assume for a moment we are at node 6 and we want to find the shortest path to node 2. Typically we would add up the distance between nodes 6, 4, 3 and 2 and see if that is shorter than going 6, 4, 5, 2 or 6, 4, 5, 1, 2. With a small graph like this with limited paths it is easy to look at the graph and know quickly which is the shortest path. However, what if the graph had as many as 3 more points and exponentially bigger path options? There will be a point where you can no longer do all the summaries in your head let alone find all options to get to a node to compare them for the shortest distance.
This is where Dijkstra’s Algorithm comes into play. It starts out at node 6 and runs through all the neighboring nodes and determines which is shorter using a “greedy” mechanism. It goes for the least cost (the shortest path to get one more node closer to the destination). In our example node 6 has only one path, to node 4 so that is a given. But the algorithm then comes to play with node 4. Is it shorter to go to node 3 or node 5. Lets say it is shorter to go to node 5. So the algorithm takes that route.
It then again validates neighboring nodes that have NOT been visited already. Since node 4 has been visited, we don’t consider it an option. We instead check out nodes 2 and 1. But in addition to these paths, we keep track of the path back from 4 to 3. If the path from 4 5 to 1 is getting expensive, it might be worth going back from 4 to node 3 and try that route instead. Either way the algorithm will not stop until all nodes have been visited and thus all paths have been run, yielding the shortest path to our destination and having a side effect of showing us the shortest paths to all nodes. So instead of just finding our one destination to node 2, once the algorithm has been ran we will know the shortest paths to nodes 4, 5, 1, 3 etc.
So lets take a look at how this works in C++….
// Dijkstra's Algorithm
// Written to C++ by Martyr2
// Dream In Code
#include <iostream>
using namespace std;
// Define the levels of the graph
const int LEVELS = 8;
// Prototype for our Dijkstra function
void Dijkstra(int *, int *, int[LEVELS][LEVELS]);
int main() {
// Define a multidimensional array of lengths between points
// Those designated -1 means no path exists beween those two points.
// Think of this as a numeric table showing relationships.
int L[LEVELS][LEVELS] = {
{-1, 5, -1, -1, -1, 3, -1, -1},
{ 5, -1, 2, -1, -1, -1, 3, -1},
{-1, 2, -1, 6, -1, -1, -1, 10},
{-1, -1, 6, -1, 3, -1, -1, -1},
{-1, -1, -1, 3, -1, 8, -1, 5},
{ 3, -1, -1, -1, 8, -1, 7, -1},
{-1, 3, -1, -1, -1, 7, -1, 2},
{-1, -1, 10, -1, 5, -1, 2, -1}
};
// An array to hold vertexes and full path distances
int Vertexes[LEVELS];
int Dist[LEVELS];
// First we just set our vertexes to a count up to the number of
// levels. Here we label vertexes 0 through 7 (thus 8 levels)
for (int i = 0; i < LEVELS; i++) {
Vertexes[i] = i;
}
// Our first vertex is a starting vertex, so set it to one
// and its distance will be 0.
Vertexes[0] = -1;
Dist[0] = 0;
// Set the distances according to our levels array defined above.
// Dist array keeps track of the legs and adds to them as we move through
// paths of the graph
for (int i = 1; i < LEVELS; i++) {
Dist[i] = L[0][i];
}
// Ok, lets start at level 1 and move to level 7
// Each time we call our function to evaluate the following...
// 1. What paths are available to us (we use the vertexes closes to our point)
// 2. How far are they away?
// 3. Take whichever is shortest path with the least cost.
for (int curlevel = 1; curlevel < LEVELS; curlevel++) {
Dijkstra(Vertexes, Dist, L);
cout << "Level " << curlevel << endl;
// Just to show what the current distances are for each path as we
// loop through the vertexs and evaluate.
for (int i = 0; i < LEVELS; i++) {
cout << Dist[i] << " ";
}
cout << endl;
// Show which vertexs have yet to be visted (-1 means visited)
for (int i = 0; i < LEVELS; i++) {
cout << Vertexes[i] << " ";
}
cout << endl;
}
return 0;
}
// Dijkstra implements the algorithm for checking the vertexs and their
// relative path distances in relation to where we are in the graph.
void Dijkstra(int *Vertexes, int *Dist, int L[LEVELS][LEVELS]) {
int minValue = 32767;
int minNode = 0;
// Loop through the vertexs to see if they have been visited
// If they haven't, check their distance and see if it is smaller than
// our current shortest distance. If so, set the new shortest distance
// to minValue and label the node as the shortest
for (int i = 0; i < LEVELS; i++) {
if (Vertexes[i] == -1) { continue; }
if (Dist[i] > 0 && Dist[i] < minValue) {
minValue = Dist[i];
minNode = i;
}
}
// Mark the new shortest distance vertex as visited
Vertexes[minNode] = -1;
// Add the distance to the overall path distance from start
// to destination. The result is a list of values at the end which will
// show the shortest paths between any two nodes.
for (int i = 0; i < LEVELS; i++) {
if (L[minNode][i] < 0) { continue; }
if (Dist[i] < 0) {
Dist[i] = minValue + L[minNode][i];
continue;
}
if ((Dist[minNode] + L[minNode][i]) < Dist[i]) {
Dist[i] = minValue + L[minNode][i];
}
}
}
The in code comments explain the process step by step. As you can see we setup a table of distances between various nodes in a graph which has 8 vertexes or nodes and 10 paths between these nodes. Start at node A which is at L[0][0] we are attempting to find the distances to all points for the shortest routes.
Just because we evaluate all routes it doesn’t mean that all routes will be used in the calculation of the shortest path to a specific node. In this case we do use all paths when reaching all nodes. As you can see from the code, I mark the list of total nodes as levels and move through them continuously as I evaluate minimum paths (Dist array). The value minValue is actually the minimum distance between two nodes. We use the original multidimensional array to currently store our accumulations between the nodes.
The result of this program is two lists of integers. The first list represents the distances between our start node and the nodes to other points. The second list represents which nodes are available (aka unvisited). By the end of the iterations through the levels, you will see that all points have become visited (all show -1) and thus we know we are done evaluating all paths.
The idea is a bit complex to get your head around, so take your time and read through the steps. This particular algorithm is great for video game design given that your character could reach a destination through a different series of paths… be it in a cave, or maze or whatever. Great for monsters who need to also find the optimal path to reach your character to kill it.
Hope you like it and enjoy! Thanks for reading. 🙂
