In this article I describe a way of modifying Dijkstra’s Alogrithm in order to find all the shortest path from a source to a node.

This article assumes you know how Dijkstra’s Algorithm works. If you don’t, see my previous post or the Wikipedia article.

The Problem

You know how to use Dijkstra’s algorithm to find the length of the shortest path to a node. You’ve even figured out how to record the path to each node. But you what you really need are all the shortest paths leading to a node.

The Idea

I can help, but to be honest, this is obvious.

In order to record the path to each node, I used an array to record which node comes before each other node in the shortest path. That is to say: prev[i] was the node that comes just before node i in the shortest path from the source to node i.

To record all the shortest paths that lead to a node, I just turned prev into a matrix with the following meaning: prev[i][0] is the number of nodes that could come before node i on a path of minimum length; prev[i][1..] are the nodes that could come before node i on path of minimum length.

The Programme

Here’s the code in C (dijkstraAll.c):

#include

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
int prev[GRAPHSIZE][GRAPHSIZE + 1]; /* prev[i] holds the nodes that could comes right before i in the shortest path from the source to i;
prev[i][0] is the number of nodes and prev[i][1..] are the nodes */

void printD() {
int i;

printf(“Distances:\n”);
for (i = 1; i <= n; ++i) printf("%10d", i); printf("\n"); for (i = 1; i <= n; ++i) { printf("%10ld", d[i]); } printf("\n"); } /* * Prints the shortest path from the source to dest. * * dijkstra(int) MUST be run at least once BEFORE * this is called */ void printPath(int dest, int depth) { int i, j; printf("-%d\n", dest); for (i = 1; i <= prev[dest][0]; ++i) { for (j = 0; j <= depth; ++j) printf(" |"); printPath(prev[dest][i], depth + 1); } } void dijkstra(int s) { int i, k, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d[i] = INFINITY; prev[i][0] = 0; /* no path has yet been found to i */ visited[i] = 0; /* the i-th element has not yet been visited */ } d[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d[i] < d[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) { if (d[mini] + dist[mini][i] < d[i]) { /* a shorter path has been found */ d[i] = d[mini] + dist[mini][i]; prev[i][0] = 1; prev[i][1] = mini; } else if (d[mini] + dist[mini][i] == d[i]) { /* a path of the same length has been found */ ++prev[i][0]; prev[i][prev[i][0]] = mini; } } } } int main(int argc, char *argv[]) { int i, j; int u, v, w; FILE *fin = fopen("dist.txt", "r"); fscanf(fin, "%d", &e); for (i = 0; i < e; ++i) for (j = 0; j < e; ++j) dist[i][j] = 0; n = -1; for (i = 0; i < e; ++i) { fscanf(fin, "%d%d%d", &u, &v, &w); dist[u][v] = w; n = MAX(u, MAX(v, n)); } fclose(fin); dijkstra(1); printD(); printf("\n"); for (i = 1; i <= n; ++i) { printf("Path to %d:\n", i); printPath(i, 0); printf("\n"); } return 0; } [/sourcecode] And here's an input file: dist.txt.
10
1 2 5
1 4 3
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4

The input file describes this graph:
djAll.png

As you can see, there are two paths from node 1 to node 3: 1 -> 2 -> 3 and 1 -> 4 -> 2 -> 3 both of length 6.

Now, what does the programme output?
Distances:
1 2 3 4 5
0 5 6 3 5

Path to 1:
-1

Path to 2:
-2
|-1
|-4
| |-1

Path to 3:
-3
|-2
| |-1
| |-4
| | |-1

Path to 4:
-4
|-1

Path to 5:
-5
|-4
| |-1

It first outputs the distances, and… yes! They’re correct.

Next, it prints those ASCII art drawings. They not drawings. They’re trees with the destination as root and the leafs as the source. To read a path from such a tree, start at a leaf (always 1) and go left, reading the first numbers you can see above.

Let’s find the paths to node 3. There are two leafs, so there are two paths of minimal length. The first one is 1 -> 4 -> 2 -> 3. The second one is 1 -> 2 -> 3. Check on the graph.

That’s it. If you’re up to a challenge, implement prev as an array of linked lists.

Good luck. Always open to comments.

Advertisements

In this article, I describe a simple (adds less than 1min of work) way to speed up Dijkstra’s Algorithm for finding the single source shortest path to every node in a graph.

In a previous post I described the simple O(n2) implementation of the algorithm. Here, I focus on a method that will probably speed up the algorithm.

Why Bother

The previous implementation of the algorithm ran in O(n2) time, where n is the number of nodes in the graph. This means that for a graph of, say 100 nodes, it would do about 100 * 100 = 100000 calculations. Considering that computers nowadays are said to be able to do about 100000000 (a hundred million) calculations per second, we’re fine, and the programme will finish in well under a second. But what if we have a graph with 100000 nodes? This might take 100 seconds to run. Now we’re in trouble. We need a faster algorithm.

The two most common ways to speed up Dijkstra’s Algorithm are to implement the finding of the closest node not yet visited as priority queues. Usually heaps or Fibonacci Heaps are used for this purpose (Fibonacci Heaps were actually invented for this).

Heaps are somewhat difficult to implement and Fibonacci Heaps are horror to implement. Incidentally, there’s a very easy of speeding it up.

Just Use Queues

The idea is to simply use queues instead of priority queues. This way provides nowhere near the same level of speedup (the algorithm is still O(n2)), but it makes it run faster, on average, by a factor of 4.

Some bad news: a carefully crafted graph could slow this algorithm down to O(n3). As a rule, graphs in real life are never like this, and, as the method isn’t widely known, test sets for contests are not written to catch this optimisation.

Now for the good news: it’s shockingly easy to write. Compare the old dijkstra1() with the new dijkstra2().

void dijkstra1(int s) {
	int i, k, mini;
	int visited[GRAPHSIZE];

	for (i = 1; i <= n; ++i) {
		d1&#91;i&#93; = INFINITY;
		visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
	}

	d1&#91;s&#93; = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited&#91;i&#93; && ((mini == -1) || (d1&#91;i&#93; < d1&#91;mini&#93;)))
				mini = i;

		visited&#91;mini&#93; = 1;

		for (i = 1; i <= n; ++i)
			if (dist&#91;mini&#93;&#91;i&#93;)
				if (d1&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d1&#91;i&#93;) 
					d1&#91;i&#93; = d1&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
	}
}

void dijkstra2(int s) {
	int queue&#91;GRAPHSIZE&#93;;
	char inQueue&#91;GRAPHSIZE&#93;;
	int begq = 0,
	    endq = 0;
	int i, mini;
	int visited&#91;GRAPHSIZE&#93;;

	for (i = 1; i <= n; ++i) {
		d2&#91;i&#93; = INFINITY;
		visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
		inQueue&#91;i&#93; = 0;
	}

	d2&#91;s&#93; = 0;
	queue&#91;endq&#93; = s;
	endq = (endq + 1) % GRAPHSIZE;


	while (begq != endq) {
		mini = queue&#91;begq&#93;;
		begq = (begq + 1) % GRAPHSIZE;
		inQueue&#91;mini&#93; = 0;

		visited&#91;mini&#93; = 1;

		for (i = 1; i <= n; ++i)
			if (dist&#91;mini&#93;&#91;i&#93;)
				if (d2&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d2&#91;i&#93;) { 
					d2&#91;i&#93; = d2&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
					if (!inQueue&#91;i&#93;) {
						queue&#91;endq&#93; = i;
						endq = (endq + 1) % GRAPHSIZE;
						inQueue&#91;i&#93; = 1;
					}
				}
	}
}
&#91;/sourcecode&#93;

What's changed? First, we <strong>define several new variables</strong>. These, together, make up the queue:

int queue[GRAPHSIZE];
char inQueue[GRAPHSIZE];
int begq = 0,
    endq = 0;

Next, during the initialisation part of the function, we mark all nodes as not being in the queue.

for (i = 1; i <= n; ++i) {
	/* OTHER INITIALISATIONS (look at the programme) */
	inQueue&#91;i&#93; = 0;
}
&#91;/sourcecode&#93;

Now, add the source node to the queue.
&#91;sourcecode language='cpp'&#93;
queue&#91;endq&#93; = s;
endq = (endq + 1) % GRAPHSIZE;
&#91;/sourcecode&#93;

What does this do? The first line add <strong>s</strong> to the end of the queue. The second line moves the end of the queue one step to the right (I'll explain a few paragraphs down). The modulo operation here is not really necessary, but I like to be consistent.

At this point we'll start looping. When do we stop? The idea here is that a node is in the queue when its neighbours need to be updated (i.e. when a new shortest path might be found leading to them). So, we stop when the queue is empty. Note that this occurs when <strong>begq == endq</strong> and <strong>not</strong> when <strong>!(begq &lt; endq)</strong>. So, <strong>while (begq &lt; endq)</strong> is incorrect because, in one case, <strong>begq</strong> will be greater then <strong>endq</strong>.

What was the first thing we did in the loop? We were supposed to find the closest node not yet visited. Now, we merely take the first node from the queue.

mini = queue[begq];
begq = (begq + 1) % GRAPHSIZE;
inQueue[mini] = 0;

Here, the first element is pop’d out of the queue, the head of the queue is moved one step to the right and the element is marked as not being in the queue. The problem with queues in general, and this one in particular is that the part of them that actually hold the elements tends to move around. Here, every insert moves the tail one step to the right and every pop moves the head one step to the right. Consider the following sequence of operations:

queue.png

Moves 1 through 8 clearly show that, while the size of the information content of the queue changes erratically, it constantly moves to the right. What happened at 9? The queue got to the end of available memory and wrapped around to the beginning. This is the purpose of (begq + 1) % GRAPHSIZE and (endq + 1) % GRAPHSIZE. It turns 7, 8, 9, etc. into 1, 2, 3, etc. But won’t endq overrun begq? No, the use of inQueue guarantees that no element will be inserted in the queue more than once. And as the queue is of size GRAPHSIZE, no overrun is possible.

So far, so good. One last modification: when we update the distance to a node, we add it to the queue (if it’s not already in it).

for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d2[mini] + dist[mini][i] < d2[i]) { d2[i] = d2[mini] + dist[mini][i]; if (!inQueue[i]) { queue[endq] = i; endq = (endq + 1) % GRAPHSIZE; inQueue[i] = 1; } } [/sourcecode]

Comparing the speed

When I first wrote this, I wanted to be able to check that it outputs correct results and I wanted to see how much faster it is. The following programme does both. The function cmpd() checks the output against that given by the simple implementation and the various clock() calls littered through the code time the two functions.

Here’s the code in C (dijkstra2.c):
Note: Source might be mangled by WordPress, consider downloading the file.

#include
#include

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d1[GRAPHSIZE], d2[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */

void dijkstra1(int s) {
int i, k, mini;
int visited[GRAPHSIZE];

for (i = 1; i <= n; ++i) { d1[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ } d1[s] = 0; for (k = 1; k <= n; ++k) { mini = -1; for (i = 1; i <= n; ++i) if (!visited[i] && ((mini == -1) || (d1[i] < d1[mini]))) mini = i; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d1[mini] + dist[mini][i] < d1[i]) d1[i] = d1[mini] + dist[mini][i]; } } void dijkstra2(int s) { int queue[GRAPHSIZE]; char inQueue[GRAPHSIZE]; int begq = 0, endq = 0; int i, mini; int visited[GRAPHSIZE]; for (i = 1; i <= n; ++i) { d2[i] = INFINITY; visited[i] = 0; /* the i-th element has not yet been visited */ inQueue[i] = 0; } d2[s] = 0; queue[endq] = s; endq = (endq + 1) % GRAPHSIZE; while (begq != endq) { mini = queue[begq]; begq = (begq + 1) % GRAPHSIZE; inQueue[mini] = 0; visited[mini] = 1; for (i = 1; i <= n; ++i) if (dist[mini][i]) if (d2[mini] + dist[mini][i] < d2[i]) { d2[i] = d2[mini] + dist[mini][i]; if (!inQueue[i]) { queue[endq] = i; endq = (endq + 1) % GRAPHSIZE; inQueue[i] = 1; } } } } int cmpd() { int i; for (i = 0; i < n; ++i) if (d1[i] != d2[i]) return 0; return 1; } int main(int argc, char *argv[]) { int i, j; int u, v, w; long t1 = 0, t2 = 0; FILE *fin = fopen("dist2.txt", "r"); fscanf(fin, "%d", &e); for (i = 0; i < e; ++i) for (j = 0; j < e; ++j) dist[i][j] = 0; n = -1; for (i = 0; i < e; ++i) { fscanf(fin, "%d%d%d", &u, &v, &w); dist[u][v] = w; n = MAX(u, MAX(v, n)); } fclose(fin); for (i = 1; i <= n; ++i) { long aux = clock(); dijkstra1(i); t1 += clock() - aux; aux = clock(); dijkstra2(i); t2 += clock() - aux; if (i % 10 == 0) { printf("%d / %d\n", i, n); fflush(stdout); } if (!cmpd()) { printf("\nResults for %d do NOT match\n", i); break; } } printf("\n"); printf("Dijkstra O(N^2):\t\t%ld\n", t1); printf("Dijkstra unstable:\t\t%ld\n", t2); printf("Ratio:\t\t\t\t%.2f\n", (float)t1/t2); /* printD(); */ return 0; } [/sourcecode] And here's a big 1200 node graph: dist2.txt.

Have fun and good luck. Always open to comments.

In this article I describe Dijkstra’s algorithm for finding the shortest path from one source to all the other vertexes in a graph. Afterwards, I provide the source code in C of a simple implementation.

To understand this you should know what a graph is, and how to store one in memory. If in doubt check this and this.

Another solution for this problem is the Bellman-Ford algorithm.

The Problem

Given the following graph calculate the length of the shortest path from node 1 to every other node.
dj1.png

Lets take the nodes 1 and 3. There are several paths (1 -> 4 -> 3, 1 -> 2 -> 3, etc.), but the shortest of them is 1 -> 4 -> 2 -> 3 of length 9. Our job is to find it.

The Algorithm

Dijkstra’s algorithm is one of the most common solutions to this problem. Even so, it only works on graphs which have no edges of negative weight, and the actual speed of the algorithm can vary from O(n*lg(lg(n))) to O(n2).

The idea is somewhat simple:

Take the length of the shortest path to all nodes to be infinity. Mark the length of the shortest path to the source as 0.

dj2.png

Now, we already know that the graph has no edges of negative weight so the a path of length 0 is the best we can come up with. The path to the source is 0, so it’s optimal.

This algorithm works by making the paths to one more node optimal at each step. So, at the kth step, you know for sure that there are at least k nodes to which you know the shortest path.

At each step, choose the node, which is not yet optimal, but which is closest to the source; i.e. the node to which the current calculated shortest path is smallest. Then, from it, try to optimise the path to every node connected to it. Finally, mark the said node as optimal (visited, if you prefer). In the previous example, the node which is closest to the source and is not yet optimal is the source. From it, you can optimise the path to nodes 2 and 4.
dj3_1.png

At this point, the only visited/optimal node is 0. Now we have to redo this step 4 more times (to ensure that all nodes are optimal).

The next node to consider is 4:
dj4.png

It’s worthwhile to note that at this step, we’ve also found a better path to node 2.
Next is node 2:
dj5.png

Finally, we look at nodes 5 and 3 (none of which offer any optimisations):
dj5.png

dj5.png

The actual code in C looks something like this:

void dijkstra(int s) {
        int i, k, mini;
        int visited[GRAPHSIZE];

        for (i = 1; i <= n; ++i) {
                d&#91;i&#93; = INFINITY;
                visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
        }

        d&#91;s&#93; = 0;

        for (k = 1; k <= n; ++k) {
                mini = -1;
                for (i = 1; i <= n; ++i)
                        if (!visited&#91;i&#93; && ((mini == -1) || (d&#91;i&#93; < d&#91;mini&#93;)))
                                mini = i;

                visited&#91;mini&#93; = 1;

                for (i = 1; i <= n; ++i)
                        if (dist&#91;mini&#93;&#91;i&#93;)
                                if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;)
                                        d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
        }
}
&#91;/sourcecode&#93;

<h4>The Programme</h4>
Putting the above into context, we get the <strong>O(n<sup>2</sup>)</strong> implementation. This works well for most graphs (it will <strong>not</strong> work for graphs with negative weight edges), and it's quite fast.

Here's the source code in C (<a href='https://compprog.files.wordpress.com/2007/12/dijkstra.c' title='dijkstra.c'>dijkstra.c</a>):

#include <stdio.h>

#define GRAPHSIZE 2048
#define INFINITY GRAPHSIZE*GRAPHSIZE
#define MAX(a, b) ((a > b) ? (a) : (b))

int e; /* The number of nonzero edges in the graph */
int n; /* The number of nodes in the graph */
long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */

void printD() {
	int i;
	for (i = 1; i <= n; ++i)
		printf("%10d", i);
	printf("\n");
	for (i = 1; i <= n; ++i) {
		printf("%10ld", d&#91;i&#93;);
	}
	printf("\n");
}

void dijkstra(int s) {
	int i, k, mini;
	int visited&#91;GRAPHSIZE&#93;;

	for (i = 1; i <= n; ++i) {
		d&#91;i&#93; = INFINITY;
		visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
	}

	d&#91;s&#93; = 0;

	for (k = 1; k <= n; ++k) {
		mini = -1;
		for (i = 1; i <= n; ++i)
			if (!visited&#91;i&#93; && ((mini == -1) || (d&#91;i&#93; < d&#91;mini&#93;)))
				mini = i;

		visited&#91;mini&#93; = 1;

		for (i = 1; i <= n; ++i)
			if (dist&#91;mini&#93;&#91;i&#93;)
				if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;) 
					d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
	}
}

int main(int argc, char *argv&#91;&#93;) {
	int i, j;
	int u, v, w;

	FILE *fin = fopen("dist.txt", "r");
	fscanf(fin, "%d", &e);
	for (i = 0; i < e; ++i)
		for (j = 0; j < e; ++j)
			dist&#91;i&#93;&#91;j&#93; = 0;
	n = -1;
	for (i = 0; i < e; ++i) {
		fscanf(fin, "%d%d%d", &u, &v, &w);
		dist&#91;u&#93;&#91;v&#93; = w;
		n = MAX(u, MAX(v, n));
	}
	fclose(fin);

	dijkstra(1);

	printD();

	return 0;
}
&#91;/sourcecode&#93;

And here's a sample input file(<a href='https://compprog.files.wordpress.com/2007/12/dist.txt' title='dist.txt'>dist.txt</a>):

<code>10
1 2 10
1 4 5
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4
</code>

The graph is given as an edge list:
<ul>
	<li>the first line contains <em>e</em>, the number of edges</li>
	<li>the following <em>e</em> lines contain <em>3</em> numbers: <em>u</em>, <em>v</em> and <em>w</em> signifying that there's an edge from <em>u</em> to <em>v</em> of weight <em>w</em></li>
</ul>

That's it. Good luck and have fun. Always open to comments.

<h4>Finding the shortest path</h4>
<strong>UPDATE</strong> In response to <strong>campOs</strong>' comment.

Now we know the distance between the source node and any other node (the distance to the ith node is remembered in <strong>d[i]</strong>). But suppose we also need the path (which nodes make up the path).

Look at the above code. Where is <strong>d</strong> modified? Where is the recorded distance between the source and a node modified? In two places:

Firstly, <strong>d[s]</strong> is initialised to be <em>0</em>.

d[s] = 0;

And then, when a new shortest path is found, d[i] is updated accordingly:

for (i = 1; i <= n; ++i)
	if (dist&#91;mini&#93;&#91;i&#93;)
		if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;) 
			d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
&#91;/sourcecode&#93;

The important thing to notice here is that <strong>when you update the shortest distance to node i, you know the previous node in the path to i</strong>. This is, of course, <strong>mini</strong>. This suggests the solution to our problem.

For every node <strong>i</strong> other than the source, remember not only the distance to it, but also the previous node in the path to it. Thus we have a new array, <strong>prev</strong>.

Now, we need to make to modifications.
First, we initialise the value of <strong>prev[i]</strong> to something impossible (say <em>-1</em>) at the start of <strong>dijkstra()</strong>.

for (i = 1; i <= n; ++i) {
	d&#91;i&#93; = INFINITY;
	prev&#91;i&#93; = -1; /* no path has yet been found to i */
	visited&#91;i&#93; = 0; /* the i-th element has not yet been visited */
}
&#91;/sourcecode&#93;

Secondly, we update the value of <strong>prev[i]</strong> every time a new shortest path is found to i.

for (i = 1; i <= n; ++i)
	if (dist&#91;mini&#93;&#91;i&#93;)
		if (d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93; < d&#91;i&#93;) {
			d&#91;i&#93; = d&#91;mini&#93; + dist&#91;mini&#93;&#91;i&#93;;
			prev&#91;i&#93; = mini;
		}
&#91;/sourcecode&#93;

Good. For every node reachable from the source we know which node is just before it in the shortest path. For the above example, we would have the following array:
<code>i - prev[i]
1 - -1
2 - 4
3 - 2
4 - 1
5 - 4
</code>

Using this, how do you get the path? Let's say you want to get to <em>3</em>. Which node comes right before <em>3</em>? Node <em>2</em>. Which node comes right before node <em>2</em>? Node <em>4</em>. Which node comes before <em>4</em>? Node <em>1</em>. We've reached the source, so we're done. Go through this list backwards and you get the path: <em>1 -&gt; 4 -&gt; 2 -&gt; 3</em>. This is easily implemented with <a href="http://en.wikipedia.org/wiki/Recursion">recursion</a>.


void printPath(int dest) {
	if (prev[dest] != -1)
		printPath(prev[dest]);
	printf("%d ", dest);
}

Here is the updated source: dijkstraWithPath.c.

Good luck.

There quite a few definitions of what a set is, but it all boils down to this:

A set defined as a collection of distinct elements, in which order is not important.

So {1, 2, 3}, {3, 4}, {} and {5, 99, -1} are all sets. Because the order of the elements is ignored, {1, 2, 3} and {3, 2, 1} is the same set. In case you’re wandering, there are exactly n! diffrent ways to write a set of n elements.

For the rest of the discussion, I’ll use sets of the form {1, 2, …, n}, so when I say a set of 3 elements, I mean {1, 2, 3}. Just remember that is not a property of sets. They can contain anything as elements, not necessarily consecutive numbers.

The set S1 is said to be the subset of the set S2, if all the elements of S1 also belong to S2.

Knowing this, it’s easy to figure out the subsets of {1, 2, 3}:
{ }
{ 1 }
{ 2 }
{ 1, 2 }
{ 3 }
{ 1, 3 }
{ 2, 3 }
{ 1, 2, 3 }

How many subsets are there? For a set of one element, there are 2 subsets: {} and {1}. For a set of 2 elements, there are 4 subsets: {}, {1}, {2}, {1, 2}. For a set of 3 elements, there are 8 subsets. Notice the pattern?
n = 1: 21
n = 2: 22
n = 3: 23

For a set of n there are 2n subsets. This is easily proved: Any subset of the set can either contain or not contain an element; so, for a subset, there are 2 states for the first element, 2 for the second element, …, 2 for the nth element; so, there are 2 states for the first element, 2 * 2 = 22 states for the first two, 2 * 2 * 2= 23 states for the first three, …, 2 * 2 * 2 * … * 2 = 2n states for all the n elements.

The problem here is how to generate all the subsets of a given set. There are a few algorithms for doing this, but in the end, only two are worth considering.

The first is this: given all the subsets of S and the element y, you can generate all the subsets of S U {y} by taking each subset of S, once adding to it y and once leaving it as it is. i.e. Knowing that {1, 3} is a subset of S, you obtain the following two subsets of S U {y}: {1, 3, y} and {1, 3}.

This does what it’s supposed to – it generates all the subsets of S, and it wastes no time. It can also be used as another way to prove that there are 2n subsets for any set of n elements. The only problem is that you need the subsets from the previous step to generate those of this step. This means that just before the end, you must have 2n – 1 subsets in memory. Considering how much memory computers have this days, it’s not particularly wasteful, but still, there’s a better way.

The better way involves using a mask. If you have the a set of n elements, a valid mask would be an array of n boolean (true/false; 1/0) elements. When you apply a mask to a set, you check each element (e) in the set and the corresponding one in the mask (m): if m is true(1), you add e to the result, otherwise, you ignore it. After applying the mask (0, 1, 0, 0, 1) to {1, 2, 3, 4, 5}, you get {2, 5}.

So, to generate all the subsets of a set of n elements, you first have to generate all the possible 2n masks of the set and then apply them.

Generating the masks is a simple problem. Basically, you just have to implement a binary counter, i.e. something that generates:
000
001
010
011
100
101
110
111

Here’s the code in C (sub.c):

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
	int i;
	printf("{ ");
	for (i = 0; i &lt; n; ++i)
		if (mask[i])
			printf("%d ", i + 1); /*i+1 is part of the subset*/
	printf("\\b }\\n");
}

/* Generates the next mask*/
int next(int mask[], int n) {
	int i;
	for (i = 0; (i &lt; n) &amp;&amp; mask[i]; ++i)
		mask[i] = 0;

	if (i &lt; n) {
		mask[i] = 1;
		return 1;
	}
	return 0;
}

int main(int argc, char *argv[]) {
	int n = 3;

	int mask[16]; /* Guess what this is */
	int i;
	for (i = 0; i &lt; n; ++i)
		mask[i] = 0;

	/* Print the first set */
	printv(mask, n);

	/* Print all the others */
	while (next(mask, n))
		printv(mask, n);

	return 0;
}

Note: The next() function generates the bits in reverse order.

Always open to comments.

A permutation of n objects is an arrangement of n distinct objects.

Wikipedia gives a slightly more detailed definition:

Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation. (For cases wherein the ordering of elements is irrelevant, compare combination and set.) For example, with the numerals one to six, each possible ordering consists of a complete list of the numerals, without repetitions. There are 720 total permutations of these numerals, one of which is: “4, 5, 6, 1, 2, 3”.

And Mathworld gives the standard mathematical definition:

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself.

Permutations are crucial to studying the behaviour of many algorithms and we’ll find a lot of intresting things about them.

For starters, what are the permutations of {1, 2, 3}? The definition says a permutation is a rearrangement of the list’s elements. So, the permutations (plural) are all the possible rearrangements of the list’s elements. This gives us six permutations:


123, 132, 213, 231, 312, 321

For convenience, we’ll only work with sets like {1, 2, 3, …, n}. In computer science, the permutations of this set is called the permutations of n. In mathematics the permutations of n means the number of permutations of the given set.

How many permutations of n are there? This is easily solved, to create a permutation one element at a time: there are n ways in which to choose the first element; then, there are n – 1 ways in which to choose the second element, so that no element repeats itself; then, there are n – 2 ways to choose the third element; …; finally, there is only one way to choose the nth element. How many posibilities does this give us? So, n ways to choose the 1st element, n(n – 1) ways for the first 2 elements, n(n – 1)(n – 2) for the first 3 elements, …, n(n – 1)(n – 2)…(n – k + 1) for the first k elements, …, n(n – 1)(n – 2)…(1) ways for all the n elements.

Now we can calculate that there are 1 * 2 * 3 = 6 permutations of 3. And … that’s right! By the way, the value 1 * 2 * 3 * … * n is usually written as n! and is called n factorial.

Great. We know what a permutation is. We know how many there are for a given set. But how do we generate them?

There are quite a few (more like dozens) methods, and I’ll describe a few here. The simplest one I can think of is this:

Let’s say you want to generate all the permutations of 3. So, you want to generate the permutations of the set {1, 2, 3}. We’ll generate the list:


123, 131, 132, 133,
211, 212, 213, 221, 222, 223, 231, 232, 233
311, 312, 313, 321, 322, 323, 331, 332, 333

That’s all the numbers you can make of length 3 using only the digits 1, 2 and 3. I start from 123 and not from 111 because there’s no permutation between 111 and 123.

Then we’ll filter the results using the rule: “A valid permutation cannot contain the same digit twice“.

Then we’ll print out what’s left.

Here’s the code in C (naiveperm.c):

#include <stdio.h>

/*!
    Generates the next try.

    If v is 1 2 1 2, after calls to

        next(v, 4);

    v will be     1 2 1 3

                1 2 1 4

                1 2 2 1

                1 2 2 2

    @return 0, if there are no more valid tries

    @return 1, otherwise
*/
int next(int v[], int n) {
    int i = n - 1;
    v[i] = v[i] + 1;
    while ((i >= 0) &amp;&amp; (v[i] > n)) {
        v[i] = 1;
        i--;
        if(i >= 0)
            v[i]++;
    }

    if (i &lt; 0)
        return 0;
    return 1;
}

void printv(int v[], int n) {
    int i;

    for (i = 0; i &lt; n; i++)
        printf("%d ", v[i]);
    printf("\\n");
}

/*!
    @return 1, if v is a valid permutation (no digits repeat)

    @return 0, otherwise
*/
int is_perm(int v[], int n) {
    int i, j;

    for (i = 0; i &lt; n; i++)
        for (j = i + 1; j &lt; n; j++)
            if (v[i] == v[j])
                return 0;

    return 1;
}

int main(int argc, char *argv[]) {
    int v[128];
    int n = 8;

    /* The initial permutation is 1 2 3 ...*/
    int i;
    for(i = 0; i &lt;= n; i++)
        v[i] = i + 1;

    while (next(v,n))
        if (is_perm(v,n))
            printv(v,n);

    return 0;
}

The code’s commented and it’s fairly simple, so there shouldn’t be any problems understanding it. Of course, I’m open to suggestions.

The next article in this series is Generating permutations: 2.