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

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%20version%2C%20December%202014.pdf?dl=0 https://www.dropbox.com/s/zy1gx1azfvvqm6i/NetSciComm%20versi...