My hunch would be to stick with Dijsktra (or A*). There's a bunch of additional routines here which appear to improve behaviour as the number of nodes becomes l

My hunch would be to stick with Dijsktra (or A*). There's a bunch of additional routines here which appear to improve behaviour as the number of nodes becomes large, but very likely lead to large coefficients in the complexity.