lukegarrigan

Dijkstra’s algorithm

The past few weeks I’ve spent a lot of time hacking my way through Advent of Code, now that the event is over I thought I’d try and implement a visual for my favourite algorithm I’ve had to implement in the Christmas period.

Dijkstra’s algorithm is used to find the shortest path between nodes in a graph. I’ve implemented a number of search algorithms that’d solve the coding challenge just as easily: including BFS, A*, A* Iterative deepening, etc.

How Dijkstra’s works

  1. Add the start node to a queue giving it a cost of 0 (It has cost nothing to get to it)
  2. Whilst there are nodes in the queue, continue to iterate through them
  3. Sort the queue by the cost (you could use a priority queue for this if your language supports it)
  4. Remove the first element of the queue (the one with the lowest cost) and find its neighbours
  5. Calculate the cost of moving to the neighbour through the current node
  6. If the cost is less than a previously set cost for the neighbour then that’s the new cost
  7. Add the neighbour to the queue

When the algorithm finishes executing you’ll have the minimum cost of reaching the destination node, and the minimum cost of reaching every node.

Here’s an implementation I wrote in JavaScript:

function solve() {
	let q = [];
	grid[0][0].score = 0;
	q.push(grid[0][0]);
	while(q.length > 0) {
		q.sort((a, b) => a.score - b.score);
		let current = q.shift();
		for (let neighbour of getNeighbours(current)) {
			let totalRiskThroughCurrent = current.score + 1;
			if (totalRiskThroughCurrent < grid[neighbour.row][neighbour.col].score) {
				grid[neighbour.row][neighbour.col].score = totalRiskThroughCurrent;
				q.push(neighbour);
			}
		}
	}
}

I’ve used a two dimensional array to try and visualise it using p5.js, similar to other blogs where I implement sorting algorithms

Using the above code gives a grid that looks like the following:

So it takes a minimum of 40 moves to get to the destination.

Making the algorithm visual

p5.js executes the draw function 60 times per second, at the moment I’m just calling my solve function once in the first frame. This is no good if we want to see the algorithm in action. To do this, rather than using a while loop, I’ll just remove an element from the queue once each frame.

So the draw function looks like this:

function draw() {
	background(220);
	for (let i = 0; i < grid.length; i++) {
		for (let j = 0; j < grid[0].length; j++) {
			grid[i][j].draw();
		}
	}

	if(q.length > 0) {
		q.sort((a, b) => a.score - b.score);
		let current = q.shift();
		for (let neighbour of getNeighbours(current)) {
			let totalRiskThroughCurrent = current.score + 1;
			if (totalRiskThroughCurrent < grid[neighbour.row][neighbour.col].score) {
				grid[neighbour.row][neighbour.col].score = totalRiskThroughCurrent;
				q.push(neighbour);
			}
		}
	}
}

And when ran:

You’ll notice that in this solution there are multiple optimal paths, hence the coloured squares merging. It would be simple enough to choose just one path to display, the code for this looks like:

function setShortestPath() {
	const end = grid[GRID_SIZE-1][GRID_SIZE-1];
	let queue = [];
	queue.push(end);
	end.solved = true;
	while (queue.length > 0) {
		let current = queue.shift();
		for (let neighbour of getNeighbours(current)) {
			if (neighbour.score === current.score-1) {
				neighbour.solved = true;
				queue.push(neighbour);
				break;
			}
		}
	}
}

I’ve continued on with the queue theme here.

I think we’d be mad not to try this on a large dataset

50×50 (Expanding 10 per frame)

100×100 (Expanding 80 per frame)

Conclusion

From these visualisations it’s easy to recognise the shortcomings of the algorithm. Dijkstra has to expand every node in order of distance from the start node, so even when the node is heading in a direction far away from the goal node it’ll get expanded. This is where A* takes the crown, using admissible heuristics A* can take a punt at the cost to get to the goal, meaning we can filter out the needless expanding of nodes that are moving away from the end state.

I hope you enjoyed this blog, don’t forget to sign up to the newsletter – Be the first to hear when we release new content, participate in weekly coding challenges, listen to more of my drivelling.

Leave a Reply