Pardon the shameless plug, but I've recently used a similarly unorthodox approach for replacing the heap inside Dijkstra's algorithm, and got a speedup - I use an array indexed by the vertices' current distances, and scan it from start to finish.

A paper is currently making the rounds, would love to hear feedback:

https://www.dropbox.com/s/zy1gx1azfvvqm6i/NetSciComm%20versi...