For path finding heuristic methods give "sub-linear" time usually (if you have a pre-processed unchanging network with random access and amortize its construction over many queries). A-star is the old school one, but folks use fancier methods today. In a server farm linear time is too slow, basically.

Interestingly, on a vehicle just doing Dijkstra's for within-city pathfinding is probably fine though if you've optimised the constant factors down. Likely no negative costs.