Note that there was not a step directly from Dijkstra to contraction hierarchies (CH); in particular, you could route using Highway hierarchies (HH) before CH came along. Both assume a fairly static network, though.
Oh yes, there have been many intermediate steps, it's a fascinating search in itself. I'd love to have a book detailing the history of shortest path algorithms. Let's hope Knuth has time to add it to TAOCP.
