Calculating the shortest path is a very hard and complex computational problem. It can be done in numerous ways, but the most popular algorithm is Dijkstras algorithm. This algorithm runs at a speed of Ordo(Number of cities + Number of roads), which is computer lingo for saying “it’s fucking slow”.
Basically it’s trying every possible solution, which takes alot of time and CPU power. It’s very similar to the Travelling salesman problem, which is known to be NP-complete. NP-complete means there is no way to find a quick solution, except trying all the possible alternatives (which takes a LONG time – solving a simple problem with only 1000 citites and 10000 roads would take a set of high powered computers many years).
You can think of NP-completeness in terms of the rubiks cube. Say you make a move on your cube, are you now closer or further from having solved the cube? You can’t tell can you? That’s because the problem in itself gives no clues as to wether you have moved closer to the solution or not. So what’s the fastest way (fewest moves) to solve a rubiks cube? There’s no way to know without having the computer try all possible ways to get a solution. That’s what NP-completeness means.
Finding the shortest path is very computationally heavy, thats why most online sites use a combination of dijkstras with some added on heuristics (a fancy word to say “more or less educated guesses”), different sites have different heuristics, which is why you get different results.
It’s basically a very hard problem to calculate the shortest path quickly, and the more cities and roads you add, the worse the problem gets. If someone would invent an algorithm that could do it quickly, they would become very famous and very rich very quickly, as that would solve the whole family of NP-complete problems (all the problems in the family can be translated in terms of eachother – so solving one would solve all of them).