Why Cheap Phones Are Slow at Finding RoutesWhy Cheap Phones Are Slow at Finding Routes

The headline finding is blunt. Memory capacity is what most strongly shapes how long Dijkstra takes. Devices with more memory finish their calculations faster, and lower-end devices take noticeably longer on the same graph.

That is awkward for navigation apps, which are expected to behave identically on a flagship and on a budget handset. Waze and Google Maps both lean on shortest path search, and the authors point out that the amount of data being processed changes how that search performs.

The proposed answer is dynamic load distribution. Instead of fixing in advance which part of the work runs where, the system watches the complexity of the calculation and the capability of the device, then reallocates as conditions change.

When a low quality device is struggling, load balancing can move work to the server. The paper reports that this transfer effectively mitigates the performance loss, at the cost of depending on the network. The server needs protection too: the mechanism adjusts in real time so that many clients asking at once do not overload it.

The design target stated in the paper is a waiting time that does not exceed one second. That number matters more than any single benchmark result, because it is a budget the whole architecture has to fit inside.

The practical takeaway: treat route finding as a shared job. Give the phone the part it can handle, hand the rest to the server when the device is weak, and measure against a waiting time the user can feel.