This years’ Advent of Code has loads of 2D grids, and makes you traverse them all to find paths of various kinds. At some point I had to implement D

Generalized Dijkstra in Haskell

submited by

Style Pass

2024-12-28 06:00:04

This years’ Advent of Code has loads of 2D grids, and makes you traverse them all to find paths of various kinds. At some point I had to implement Dijkstra’s algorithm, in Haskell. In trying to make my implementation reusable for the following days, I realized that Dijkstra’s algorithm is actually way more general than I remembered (or was taught)! In short, weights don’t have to be real-valued!

In this post, I describe a general interface for the algorithm, such that we can implement it exactly once and use it to compute many different things.

This article is a literate Haskell file, so feel free to download it and try it 1 for yourself! As such, let’s get a few imports and language extensions out of the way:

Let’s recall the problem statement that Dijkstra’s algorithm solves, and the pseudo-code of the algorithm. If you know that already, you can skip to the next section.

It’s been a while since I had to use any formalism to talk about graphs proper. So I will be using the notations from the Cormen book that I just looked up for a refresher.