Dijkstra algorithm for iPhone
With sdk 3.0 it is easy to use the GPS functions in iPhone, but it is clearly forbidden to use Google Maps. I think it has two meanings:
- You will have to provide the cards yourself.
- You will have to calculate the shortest routes yourself.
I know calculating the shortest route has puzzled mathematicians several times, but both Tom Tom and Google are doing an excellent job so the problem seems to be solved. Searching the "web" without being a mathematician himself, I came across the Dijkstra Algorithm . Are there any of you who have successfully used this algorithm in a Map-like app on the iPhone? Do you agree to share it with me / the community? Will this be the correct approach or other options? Thank you so much for your attention.
Dijkstra's algorithm is designed to find the shortest path to all nodes (from one start node). Game programmers use directed searches like A *. If Dijkstra first processes the node closest to the original position, A * processes the one that evaluates to be closest to the final position
The way it works is you provide a cheap "estimate" function from any given position to the end point. A good example is how far the bird flew there. A * adds this to the current distance from the start for each node, and then selects the node that appears to be on the shortest path.
The better your score, the less time it will take to find a good path. If this time is too long, you can find a path on a simple map and then another on a more complex map to find a route between the places you found on a simple map.
Update After a lot of searching, I found an article article on A * so you can read
a source to share
I don't think Dijkstra's algorithm would be useful for display in the real world, because as Tom Leys said (I would comment on his post, but I miss the reputation) it requires one starting point. If the starting point changes, everything needs to be recalculated, and I guess it will be quite slow on a device like the iPhone for a significantly large dataset.
a source to share
Dijkstra's algorithm is O (m log n) for n nodes and m edges (for one path) and is efficient enough for network routing. This means that it is efficient enough for a one-time computation.
In short, Dijkstra's algorithm works as follows:
Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key
Repeat:
Pop the node with the lowest depth from the priority queue
Record the node that you came from so you can track the path back
Mark the node as having been visited
If this node is the destination:
Break
For each neighbour:
If the node has not previously been visited:
Calculate depth as depth of current node + distance to neighbour
Insert neighbour into the priority queue at the calculated depth.
Return the destination node and list of the nodes through which it was reached.
Contrary to popular belief, Dijkstra's algorithm is not necessarily the shortest trajectory calculator of all pairs, although it can be adapted for this.
You will need to get a graph of the streets and intersections with the distances between the intersections. If you had this data, you could use Dijkstra's algorithm to calculate the shortest route.
a source to share
If you look at the technology tomtom calls "IQ routes", they measure your actual speed and route times over the time of day. This makes the arrival time more accurate. So the expected arrival time is more based on facts http://www.tomtom.com/page/iq-routes
a source to share
Route calculation using the A * algorithm is fast enough on an iPhone with offline map data. I have experience doing this commercially. I use the A * algorithm as described on Wikipedia and store the road network in memory and reuse it; once it is loaded, routing even to a large area, such as Spain or the western half of Canada, is almost instantaneous.
I am taking data from OpenStreetMap or elswhere and transforming it into a directed graph, assuming (which is the correct way to do this according to those in the know) that there are two roads connected to it that share a point with the same ID. I assign weights to the different road types based on the expected speeds, and if part of the road is one-way, I only create one arc; two-way roads get two arcs, one in each direction. This is pretty much everything except special code to prevent dangerous turns and enforce routing restrictions.
a source to share
This was discussed earlier here: What algorithms calculate directions from point a to point b on the map?
a source to share