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.

None, very irrelevant and where it applies very minor problem vs all the others ;)

For most use cases shortest path is super simple and fast problem on modern PCs. So might be useful on extra large synthetic networks. Neural nets?, Trading logs?, Image processing?

Also negative weights are rare in real life applications. And def not in what you would consider normal path planning.