Finding All Paths of Minimum Length to a Node Using Dijkstra’s Algorithm

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 <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 */
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;
}

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:

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.