Consider a Dijkstra optimization

[dabrahams]

The optimization is described here, with references to proofs of correctness and complexity.

[davecom]

Thank you, that's very interesting. Have you considered publishing it as a paper?