Hmm, wouldn't Dijkstra's be V E + V^2 log V? I take your point though. I suspect that I was dazzled by the cache locality advantages of dynamic programming and

Hmm, wouldn't Dijkstra's be V E + V^2 log V? I take your point though. I suspect that I was dazzled by the cache locality advantages of dynamic programming and skeptical that messing about with a bunch of heap nodes would be faster, but looking at it now I bet you're right that knocking one of those Vs down to a log V would help. Thanks for the feedback!