Except it’s fun: Navigation apps in 3 minutes
If you’re anything like me, you too cannot drive anywhere without setting up Waze… even if it’s 5 minutes away. I was always impressed when I was little and my dad could take me places by just remembering routes, and even shortcuts or guessing traffic patterns!
But how do we actually do that? And more importantly, how do navigation tools like Waze or Google Maps do that, at such high precision?
Today’s short blog: Why graph theory is to thank for making it on time for that important meeting on an early Tuesday. ☕
1. The logic
So, you want to get from your place to the closest coffee shop. Routing complete: About 8 minutes drive, enjoy! 🚗 But… how??
In its simplest form, it’s a game of finding the shortest path between two points, with one added rule: traffic laws.
The most important ones, for our scope, include direction of travel, speed limits, junctions and of course, length of travel. The length is not a straight line though, but rather a combination of multiple, connected streets. This makes for some interesting and unexpected quirks, such as: Turn right now ➡️.. despite your final destination being leftwards of your current position!
Using a combination of the above, the shortest available and valid route is chosen, and the estimated time is calculated as a function of its length (in km) and existing speed limits (in km/h)*.
*Plus A LOT more things.. we’ll soon get to!
But — how do we pick the route to begin with? Here we turn to math, and algorithms like Dijkstra’s to help us choose the shortest path.
2. The math
Let’s first define two crucial concepts:
- Nodes/Vertices: Think of every time you have the ability to take a right or a left, instead of going straight. That’s what we call an intersection or junction.
- Edges: This is a (part of a) street you travel, from one junction to the next one.
In other words, vertices are your decision points (keep going straight? make a left?), and edges represent the distances you travel. Clearly, more vertices add complexity, whilst more edges add distance and, consequently, time.
Get Alex Caian’s stories in your inbox
Join Medium for free to get updates from this writer.
But we know streets are not all the same length. Therefore, we want a way to penalise longer streets. This final concept is that of a weight. Think of weights as penalties for longer streets, but also for intersections (since they’re often accompanied by traffic lights).
So — What happens in the background is now a strictly mathematics problem:
How can I reach my destination with the smallest sum of weights possible.
In other words, the roadmap system is treated like a graph/network of streets (edges) and intersections (vertices), and our trusty navigation system is solving the aforementioned problem with it. You might also care about visiting the fewest edges (want to only use main streets), or maybe fewest intersections (don’t like waiting at stoplights!).
Pretty simple, right? Or ….
3. The reality
Our system more closely resembles this:
Of course, it had to be a lot more complex in reality. :D The good news however, we now know how to interpret everything driving throws at us: weights !
The real strength of modern navigation lies in the realtime insights. At the end of the day, such apps are recommender systems, calculating a route based on both the graph elements discussed, but also dynamic insights such as: traffic, estimations (from previous days data), road status, human indicators (other drivers) and many, many more.
The accuracy of these systems is a compounding result of all of the above, especially the precise satellite location helping us recalculate egdes’ weights in a matter of seconds.
Recommender systems is something we can dedicate a whole new blog (or more) to, but for now… I’m just grateful I get to use Waze on every commute. I hope you too trust it a bit more, now that you know a little bit about how it works. :) See you next time! 👋
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I’m open to answering any other questions in private — just drop me a message on LinkedIn or Email :)
Find me on: Github || LinkedIn or via email at axl_acc@yahoo.ro
