update: I was finding problems with my backlink based algorithm, so I decided to try the other idea: traverse links in order of hop-length. That worked, but was using a sorted array. Okay so there is an data structure for this: a Heap. On the wikipedia page, I read the line:

Heaps are also crucial in several efficient graph algorithms such as Dijkstra's algorithm

Oh yeah I should have read that. On that page I read:

What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.

Dang, now I feel dumb.
Months fumbling around with this problem and Dijkstra came up with it in 20 minutes!

Although, the problems we are describing is slightly different. In the end, we only care about the distance to the node, not the path. But... that isn't a very big difference.