I went down a similar path, but only saw about a 770x speedup. Mine went from 36 minutes to 2.8 seconds. I was working in Idris. I knew better, but figured the

I went down a similar path, but only saw about a 770x speedup. Mine went from 36 minutes to 2.8 seconds. I was working in Idris. I knew better, but figured the data was small enough that I could just do a linear scan for the next node instead of implementing a heap. In the fast version I ended up using a SortedMap (Int,(Int,Int)) () for the queue. I only added points to the queue as I discovered them (neighbors of points that I visit), so it maxed out at 913 elements. It sounds like OP may have started out with all points in their queue?