Linked Questions
14 questions linked to/from What algorithms compute directions from point A to point B on a map?
72
votes
9
answers
8k
views
A* Algorithm for very large graphs, any thoughts on caching shortcuts?
I'm writing a courier/logistics simulation on OpenStreetMap maps and have realised that the basic A* algorithm as pictured below is not going to be fast enough for large maps (like Greater London).
...
10
votes
7
answers
32k
views
Which algorithm does Google maps use to compute the direction between 2 points?
I wonder which algorithm Google maps use to compute the direction between 2 points ? Has Google ever mentioned about it ?
p/s : I am asking the algorithm which google use to find the shortest route ...
22
votes
3
answers
10k
views
Calculating the shortest route between two points
I have been working in the past weeks on a multiplayer HTML5 game, using nodejs and websockets.
I've been stuck in this problem for a little while.
Imagine that I have this tilesheet map implemented ...
1
vote
7
answers
3k
views
Dijkstra algorithm for iPhone
It is possible to easily use the GPS functionality in the iPhone since sdk 3.0, but it is explicitly forbidden to use Google's Maps.
This has two implications, I think:
You will have to provide maps ...
4
votes
4
answers
4k
views
How to calculate distance between two points in Android FAST for MANY points
I have around 1000 points. I'm trying to group this points base on distance. Im using the harversine formula, but it seems to be super slow. In android for 1000 points takes 4 seconds. In my local ...
3
votes
2
answers
8k
views
Optimizing Dijkstra for dense graph?
Is there another way to calculate the shortest path for a near complete graph other than Dijkstra? I have about 8,000 nodes and about 18 million edges. I've gone through the thread "a to b on map" and ...
4
votes
2
answers
16k
views
Algorithm/Method Use By Google Maps For Finding the Path Between Two Cities
Recently I had a job interview they asked me "Which method is use by google maps for finding the shortest path between two cities?". I didn't had the answer to that question but I guessed they use the ...
6
votes
4
answers
3k
views
Heuristic for A*-Algorithm with irregular distances between nodes
I am currently working on an implementation of the A* Algorithm with irregular distances between two nodes. The graph containing the nodes is a directed and weighted graph. Every node is connected to ...
4
votes
1
answer
3k
views
Algorithm behind distance calculations in The Google Distance Matrix API
How does the Google Distance Matrix API calculate the distance from point A to B. Often there are multiple ways to go from A to B and the question is how Google prioritizes different routes to find ...
0
votes
1
answer
1k
views
Buses scheduling - relational database or nosql
I'm trying to store buses schedules into database and I'm wondering which database model is suitable for my case.
I have bus operators, each operator has several routes, each route has several turns, ...
0
votes
2
answers
880
views
How does Google Maps and Nokia Maps generate routes from point to point
I will like to know if anyone has an idea on the concept behind point to point route generation on google maps and nokia maps. What logic was used to determine the route and generate directions from ...
0
votes
0
answers
940
views
Route optimization by address and by Lat/long
I just try understand if there any free (open-sourse) code /api where you can give list of coordinates, give them start/end destination get in response route optimized
I find:
https://graphhopper....
1
vote
4
answers
330
views
Datastructure for googlemap like application?
I am doing a maprouting application. Several people have suggested me, that I do a datastructure where I split the map in a grid. In theory it sounds really good, but I am not to sure because of the ...
1
vote
1
answer
41
views
What algorithms are used in describing routes
In this question the author asked what algorithms compute directions from point A to point B on a map and the answer was
Dijkstra's does work, with a couple of modifications
But I am also curious ...