The Science Behind Google Maps | Route Finding Algorithms

Route finding algorithms are crucial for the function of your favourite apps such as Google Maps or Citymapper.

How do they work? In this video, we will explore how graph theory and pathfinding algorithms are crucial to the function of these apps.

[marya]

This was so interesting and informative, yet simply and briefly explained. Thank you so much for this video! I especially loved the diagram clearly depicting the nodes and edges. Really helped to contextualise what you were discussing, even if Dijkstra's algorithm may not be used by Google Maps. Will definitely be subscribing after this :)

[tinkering_geek]

This is fine for predefined data, but how are the nodes and times derived? Of the 100's of millions of nodes and edges, they must be auto generated? and if the source is an electronic map how does the algorithm follow the road to from node to node to calc the time between nodes. This is the question I wish I understood. I doubt an object of sort guided along the path keeping within the boundaries of the drawn road discovering the nodes as it goes and are all intersections nodes? If some nodes lea to dead ends then does it explore that path? I think the real solutions is orders of magnitude more complex that an alogorithm considering one way roads, dead ends, toll roads, rail crossings. Its either incredibly complex or incredibly cleaver probably both.

[hyungnim]

does dijkstra algorithm contain accuracy and error? my professor keep asking me that

[codyking]

Maps software is probably not using plain Dijkstra's. Most likely A* or something else.

[hesterclapp]

How does this work with timetables, where a journey's duration relies on what time you are traveling?