The K-Shortest Paths Algorithm in C++

Introduction

Following on from a previous post which was concerned with finding all possible combinations of paths between communicating end nodes, this algorithm finds the top k number of paths: first the shortest path, followed by the second shortest path, the third shortest path, and so on, up to the k-th shortest path.

This policy of restricting the number of paths found might be useful in situations where you wish to only consider a relatively short subset of the total possible number of combinations of of paths. This is of particular relevance as the size of the network increases, leading to an explosion in the number of possible combinations (and hence memory resources).

For a description of Yen’s original algorithm see this paper: ‘A New Implementation Of Yen’s Ranking Loopless Paths Algorithm’. Another good description of the k-shortest paths algorithm can be found here.

Implementation

I have not re-invented the wheel here. I have recently been experimenting with a C++ example that is already freely available online at this following link. From what I tried out so far, this appears to work accurately with no perceptible problems. Notice that C# and Java implementations are also available:

http://code.google.com/p/k-shortest-paths/downloads/list.

The code essentially provides a graph-handling class and an algorithm class that acts upon the graph class to implement the Yen’s shortest path algorithm. I have taken this code and modified it a little so that the user is not only able to use the Graph class to import example networks from text files, but use it to create new networks by adding nodes and interconnecting links as well.

Example usage

Consider the following 15-node network, that contains a combination of bi-directional and uni-directional links:

So that the user can construct network topologies from scratch, and not just from input files, I have added the Link struct in the header file Graph.h. To create the above network for example, you would create a variable array of Link structs similar to this:

link lks[] = {      {0, 1},
					{0, 12},
					{0, 13},
					{1, 0},
					{1, 2},
					{2, 1},
					{2, 3},
					{2, 5},
					{3, 2},
					{3, 4},
					{4, 3},
					{4, 5},
					{4, 6},
					{5, 2},
					{5, 4},
					{5, 7},
					{6, 4},
					{6, 8},
					{7, 5},
					{7, 10},
					{8, 6},
					{8, 10},
					{9, 8},
					{9, 11},
					{10, 7},
					{10, 8},
					{10, 11},
					{11, 9},
					{11, 10},
					{11, 12},
					{11, 13},
					{12, 11},
					{13, 11},
					{13, 14},
					{14, 1},
					{14, 5},
					{14, 13} };

Please note that when leaving out the Link weight field and just using the two Link end nodes, as I have done above, will result in path lengths based on the least number of hops rather than or as well as the least cost routes, since this is akin to setting all Link weight values equal to zero.

And to find for example the top 5 shortest paths from node 1 to node 8 in this 15-node network example, we simply supply testYenAlg with these required parameters like so:

 int k = 5;
	int array_size = sizeof( lks ) / sizeof( lks[ 0 ] );
	int start = 1;
	int end = 8;
	int nodes = 15;


	testYenAlg( k, 
		        lks, 
				array_size, 
				start,
				end, 
				nodes );

Which would give the following output:

Microsoft Visual Studio 2010 project downloadable from here.

Microsoft Visual Studio 2003 project downloadable from here.