Dijkstra’s is a pretty cool algorithm designed in the 50’s, which is still pretty much state of the art when calculating shortest paths in general graphs. It’s pretty fast too: almost linear in the number of edges. Sometimes this is still too slow though! If your road network is very big (the world has hundreds of millions of ‘edges’) and you want many millions of routes, waiting a couple of seconds for each one is not nice. ORTEC is a Dutch company that (among many other things) makes software that optimizes routes for trucking and package delivery companies. They use some clever algorithm called Highway Node Routing that can outperform classic Dijkstra’s by a factor of 1000x.
One of their engineers will drop by VIA and explain how the algorithm accomplishes this and a little bit of the programming tricks to squeeze every bit of performance out of their code.