Modeling Google Maps Using Graph Theory
Mathematics can be applied to many problems from simple daily life to very complex problems, like traveling to Space. To make this possible Computer science plays a huge role to be a bridge between hardcore math and computers. Computer science heavily relies on mathematics theories and their proofs when it comes to applying to tackle the problem by creating software. One of the most important and widely-used theories is Graph Theory in computer science.
What is Graph Theory?
Graph Theory — is the study of graphs, which are mathematical structures used to model pairwise relations between objects. Graph is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). [Wikipedia]. It might sound complicated, but we have already seen graph representation in our daily life, for example, file structure, organizations hierarchy, or google maps.
Modeling a Map.
In my last term of school at Make School, I learned Graph Theory and how to apply it to model real-world problems. I chose to make a very naive version of own Google Maps using the knowledge I have learned during class. It was fun, at the same time, challenging project. I have experienced how engineers come up with a solution. Why I chose to make this project was that I have always been curious how google maps find me multiple routes and choose me the fastest one and show me an estimated time to get the destination. My project proposal:
This project will tackle the common problem of modeling maps. When we use maps we always want choose the fastest route or sometimes safest route. The entire premise of Google Maps is using a big giant graph with nodes and edges to figure out fastest or shortest way to travel. That’s all Google Maps is–a big graph with lots of nodes and edges.
So, I applied graph theory to solve these following common cases on my project:
- The shortest path from A to B(using Dijkstra’s algorithm)
- The busiest intersection(most connected vertex)
- Find near me(find all location nearby specified miles)
While I was working on this project I have seen how graph theory can be used a huge deal of google maps application. So, my first question was how to find the shortest route from A to B, let’s say my daily route from home to school. I used Dijkstra’s algorithm to find the shortest path between two vertices here is how it looks like in code.
You can learn about my project at my GitHub profile. As I said above, we can tackle a lot of problems and model them using Graph Theory. It all depends on our imagination. Thank you for reading up to this point.
