Dijkstra’s Algorithm code in C++

Dijkstra’s algorithm is a famous algorithm that calculates the routes and distances from a start node to all other nodes in a connected graph where all the distances are positive.

Here is a version which I wrote in C++. My aim here was to try to create a version that was easy to read, rather than the most efficient version. I used the excellent Introduction to Algorithms book as a reference for my version of Dijkstra’s. This version is implemented using STL vectors to store the edges and nodes. I might later modify it to use adjacency lists and priority queues to produce a more efficient implementation.

First off is my Node and Edge class. You’ll note that the objects add themselves to the nodes and edges vectors as they are constructed.

vector<Node*> nodes;
vector<Edge*> edges;

class Node
{
public:
	Node(char id) 
		: id(id), previous(NULL), 
		distanceFromStart(INT_MAX)
	{
		nodes.push_back(this);
	}
public:
	char id;
	Node* previous;
	int distanceFromStart;
};


class Edge
{
public:
	Edge(Node* node1, Node* node2, int distance) 
		: node1(node1), node2(node2), distance(distance)
	{
		edges.push_back(this);
	}
	bool Connects(Node* node1, Node* node2)
	{
		return (
			(node1 == this->node1 &&
			node2 == this->node2) ||
			(node1 == this->node2 && 
			node2 == this->node1));
	}
public:
	Node* node1;
	Node* node2;
	int distance;
};

Next up is my code to construct a simple test graph. The starting node is initialised with a distance of 0. Dijkstra’s algorithm is then called before the results are printed out. Underneath the code is a diagram of what this graph looks like.

void DijkstrasTest()
{
	Node* a = new Node('a');
	Node* b = new Node('b');
	Node* c = new Node('c');
	Node* d = new Node('d');
	Node* e = new Node('e');
	Node* f = new Node('f');
	Node* g = new Node('g');

	Edge* e1 = new Edge(a, c, 1);
	Edge* e2 = new Edge(a, d, 2);
	Edge* e3 = new Edge(b, c, 2);
	Edge* e4 = new Edge(c, d, 1);
	Edge* e5 = new Edge(b, f, 3);
	Edge* e6 = new Edge(c, e, 3);
	Edge* e7 = new Edge(e, f, 2);
	Edge* e8 = new Edge(d, g, 1);
	Edge* e9 = new Edge(g, f, 1);

	a->distanceFromStart = 0; // set start node
	Dijkstras();
	PrintShortestRouteTo(f);

	// Node / Edge memory cleanup snipped
}

Dijkstra's algorithm

Here is the actual algorithm implementation. We remove the node with the smallest distance from the list of nodes, and then calculate all the minimum distances. We repeat until there are no more nodes left.

void Dijkstras()
{
	while (nodes.size() > 0)
	{
		Node* smallest = ExtractSmallest(nodes);
		vector<Node*>* adjacentNodes = 
			AdjacentRemainingNodes(smallest);

		const int size = adjacentNodes->size();
		for (int i=0; i<size; ++i)
		{
			Node* adjacent = adjacentNodes->at(i);
			int distance = Distance(smallest, adjacent) +
				smallest->distanceFromStart;
			
			if (distance < adjacent->distanceFromStart)
			{
				adjacent->distanceFromStart = distance;
				adjacent->previous = smallest;
			}
		}
		delete adjacentNodes;
	}
}

Here are the supporting functions. The first function removes and returns the node with the smallest distance from the list.

The next returns a new vector containing all the nodes which are adjacent to the node that we pass in.

The third returns the distance value of an edge which directly connects the two nodes.

The final one checks if a node is in the list of nodes.

// Find the node with the smallest distance,
// remove it, and return it.
Node* ExtractSmallest(vector<Node*>& nodes)
{
	int size = nodes.size();
	if (size == 0) return NULL;
	int smallestPosition = 0;
	Node* smallest = nodes.at(0);
	for (int i=1; i<size; ++i)
	{
		Node* current = nodes.at(i);
		if (current->distanceFromStart <
			smallest->distanceFromStart)
		{
			smallest = current;
			smallestPosition = i;
		}
	}
	nodes.erase(nodes.begin() + smallestPosition);
	return smallest;
}

// Return all nodes adjacent to 'node' which are still
// in the 'nodes' collection.
vector<Node*>* AdjacentRemainingNodes(Node* node)
{
	vector<Node*>* adjacentNodes = new vector<Node*>();
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		Node* adjacent = NULL;
		if (edge->node1 == node)
		{
			adjacent = edge->node2;
		}
		else if (edge->node2 == node)
		{
			adjacent = edge->node1;
		}
		if (adjacent && Contains(nodes, adjacent))
		{
			adjacentNodes->push_back(adjacent);
		}
	}
	return adjacentNodes;
}

// Return distance between two connected nodes
int Distance(Node* node1, Node* node2)
{
	const int size = edges.size();
	for(int i=0; i<size; ++i)
	{
		Edge* edge = edges.at(i);
		if (edge->Connects(node1, node2))
		{
			return edge->distance;
		}
	}
	return -1; // should never happen
}

// Does the 'nodes' vector contain 'node'
bool Contains(vector<Node*>& nodes, Node* node)
{
	const int size = nodes.size();
	for(int i=0; i<size; ++i)
	{
		if (node == nodes.at(i))
		{
			return true;
		}
	}
	return false;
}

And finally here is the code which prints out the route between our start node ‘a’ and the destination node ‘f’. It starts at the destination node and then works backwards using the previous pointer in each node.

void PrintShortestRouteTo(Node* destination)
{
	Node* previous = destination;
	cout << "Distance from start: " 
		<< destination->distanceFromStart << endl;
	while (previous)
	{
		cout << previous->id << " ";
		previous = previous->previous;
	}
	cout << endl;
}

Update: 7th September 2008

I have now uploaded a zip file containing the Visual C++ Express Solution file and source code for this project – Dijkstra’s Source Code (8kb).

43 Comments on “Dijkstra’s Algorithm code in C++”

  1. Hey. Just wanted to say that this was the best version i found online! Very easy to read.

    However, it does not calculate all ways?

    i have the points
    A B C D
    ———
    1. A->B->C->D
    2. A->D

    The road 1. does not show up even though it is a smaller distance. It takes the road directly from A to D. Maybe it is just me who did not check the algorithm to a 100% but just wanted to say that.

    Anyways, good work!

  2. Hi jonte – I tried your test using the below code and it correctly picked A-B-C-D. You’d have to give me more details to prove there is a bug.

    Node* a = new Node(‘a’);
    Node* b = new Node(‘b’);
    Node* c = new Node(‘c’);
    Node* d = new Node(‘d’);

    Edge* e1 = new Edge(a, b, 1);
    Edge* e2 = new Edge(b, c, 1);
    Edge* e3 = new Edge(c, d, 1);
    Edge* e4 = new Edge(a, d, 4);

    a->distanceFromStart = 0; // set start node
    Dijkstras();
    PrintShortestRouteTo(d);

  3. thks gr8 help. not clear why it chose the A D node .if like u said picked the minimum distance

  4. The A-D-G-F is the route with the minimum distance. It has a length of 4.

    For example A-C-E-F has a distance of 6 and A-C-B-F also has a distance of 6.

  5. Hi,
    Please can you assist me how can i implement this codes??

    I run MS Visual C++ 2008 Express Edition. I created new project choosing Win32 Project…creating an empty console project…and then I added new C++ file(.cpp) inside the source files…but it didn’t work!!!
    can you please help about that so then I can reference your work??

  6. Hi
    The code needs to tchar.h I Couldn’t compile the code. Do you can submit the tchar.h ? please so Ican compile the code.

  7. Hi Sara, tchar.h should be in your VC++ install folder. For example on my computer it is at C:\Program Files\Microsoft Visual Studio 10.0\VC\include\tchar.h

    Perhaps you should try reinstalling VC++? Maybe your install is corrupt/incomplete.

  8. Thank you very much rml

    I appreciate it. I will study the codes and try to modify it according to my needs.

  9. Hi!! I have a problem with your code : when I want to launch it I have this message : C:\Documents and Dijkstras.cpp|38|error: ‘INT_MAX’ was not declared in this scope|

    Can you help me please ?

  10. Hi Eddy, Did you try downloading the project as a .zip and importing it into Microsoft Visual Studio Express C++ 2010? The full source in the zip contains the #includes that will load the INT_MAX constant.

  11. Hi and thank you for answering as fastly ! I don’t work with Visual Studio Express C++ 2010 but with codeblocks. Does it change something ?

  12. Hi Eddy, Yes if you aren’t using Visual Studio Express C++ 2010 you’ll have to figure out what changes you need to make. Start with the first error message and fix each one until it works.

    INT_MAX is not defined. Either find a header that includes this definition, or you might have to rename or define INT_MAX yourself.

  13. Hi, nice work, but can someone supply a example on how would this be implemented in a c++/mfc dialog program…I’m having problem with it….the vectors are not been updated…

  14. ExtractSmallest() runs in linear time, so it is not very efficient. If you used a heap or binary search tree you can get the smallest much faster.

  15. Hi, is it possible to post the Node/Edge cleanup code? I’m trying to get this to work in a do-while loop with different starting nodes, but somehow I can’t seem to get it to work after the first iteration.

    After the first iteration, the program seems to not bother about the new starting node and just uses the first start node for the rest of the program.

  16. Hi silverblade, I went to look at the original code expecting to copy and paste it in here for you – but I discovered that I never wrote the cleanup code! I just left it as a TODO for later :o

  17. Hi thanks for the reply, currently the only way I can think of for this to do multiple iterations, is to reconstruct the weighted graph for every iteration, which is terribly inefficient.

    Basically what I have now is:
    Node* a = new Node(‘a’);
    Node* b = new Node(‘b’);
    Node* c = new Node(‘c’);
    Node* d = new Node(‘d’);

    Edge* e1 = new Edge(a, c, 1);
    Edge* e2 = new Edge(a, d, 2);
    Edge* e3 = new Edge(b, c, 2);
    Edge* e4 = new Edge(c, d, 1);

    //assume this is the 1st loop
    a->distanceFromStart = 0; // set start node
    Dijkstras();
    PrintShortestRouteTo(d); //correct path printed
    a->distanceFromStart = INT_MAX //attempts to un-set the start node

    //assume this is the 2nd loop onwards
    b->distanceFromStart = 0; // set new start node
    Dijkstras();
    PrintShortestRouteTo(d); // at this point it still shows the path for A to D

    Any ideas as to why this is happening? Much thanks!

  18. Hi silverblade, I think you’ll need to reset the previous and distanceFromStart variables in all the nodes before trying to calculate a new route.

  19. hi,
    this code eventually works good, but its not effective.
    for a complex senario, with 100000 nodes, this algorithem works truly bad.

  20. Do you know what you would need to modify to make this work for directed graphs? Thanks :)

  21. Hi I’m a noob in c++ but I really wanna try this code. I understand a part but I think I shoul debbug it to understand everything. Should I choose windows form application,win32 console application or clr console application???

  22. Hi, I’d suggest you create a win32 console application. This is the simplest and easiest application type to get started with. Any output will appear in a DOS window.

  23. Kay:
    The original algorithm as shown in Cormen/Leiserson/Rivest does work with directed graphs, but this implementation has a “Connects()” predicate which castrates the algorithm unnecessarily.

  24. I’ve fixed some of the issues with this code sample, and posted the changes here if you’re interested. I’ve given credit for the original code to the author of this blog, and linked to this blog post specifically.

    http://nic-gamedev.blogspot.com/2013/03/djikstras-algorithm.html

    The issues I’ve fixed are:
    * Encapsulated the code into classes, for cleanliness and usability.
    * A graph class that handles the nodes, edges, and algorithm takes care of cleaning up the pointers, so the user isn’t forced to. Makes it less likely you’ll end up with memory leaks.
    * Allows for uni-directional edges (directed graph) as well as bi-directional edges.
    * Allows for querying the graph for a path without destroying the node list, this prevents the user from having to recreate the node graph after each query.

Leave a Reply

Your email address will not be published. Required fields are marked *

Do NOT fill this !