What algorithms compute directions from point A to point B on a map?

by

Speaking as someone who spent 18 months working at a mapping company, which included working on the routing algorithm… yes, Dijkstra’s does work, with a couple of modifications:

  • Instead of doing Dijkstra’s once from source to dest, you start at each end, and expand both sides until they meet in the middle. This eliminates roughly half the work (2*pi*(r/2)^2 vs pi*r^2).
  • To avoid exploring the back-alleys of every city between your source and destination, you can have several layers of map data: A ‘highways’ layer that contains only highways, a ‘secondary’ layer that contains only secondary streets, and so forth. Then, you explore only smaller sections of the more detailed layers, expanding as necessary. Obviously this description leaves out a lot of detail, but you get the idea.

With modifications along those lines, you can do even cross-country routing in a very reasonable timeframe.

More Related Contents:

  1. Algorithm to beat Strassen’s Algorithm
  2. What does O(log n) mean exactly?
  3. HSL to RGB color conversion
  4. What exactly does big Ө notation represent?
  5. Select k random elements from a list whose elements have weights
  6. How are ssl certificates verified?
  7. How to find the intersection point between a line and a rectangle?
  8. Generate an integer that is not among four billion given ones
  9. Find duplicates in an array, without using any extra space
  10. How to generate Sudoku boards with unique solutions
  11. How to delete in a heap data structure?
  12. How can I detect common substrings in a list of strings
  13. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  14. Efficiently reverse the order of the words (not characters) in an array of characters
  15. Scheduling algorithm for a round-robin tournament?
  16. O(klogk) time algorithm to find kth smallest element from a binary heap
  17. Calculating permutations in F#
  18. Painter puzzle – estimation
  19. Approximate string matching algorithms
  20. Skip List vs. Binary Search Tree
  21. Previous power of 2
  22. Fast solution to Subset sum
  23. Generating shuffled range using a PRNG rather than shuffling
  24. Find out which combinations of numbers in a set add up to a given total
  25. Print the biggest K elements in a given heap in O(K*log(K))?
  26. Difference between Big-Theta and Big O notation in simple language
  27. How can I perform Collision Detection on rotated rectangles? [closed]
  28. Find the pair across 2 arrays with kth largest sum
  29. algorithm to check a connect four field
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment