Dijkstra algorithm for iPhone

Question

Hello all! 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:

1. You will have to provide maps yourself
2. You will have to calculate the shortest routes yourself.

I know that calculating the shortest route has puzzled mathematicians for ages, but both Tom Tom and Google are doing a great job, so that issue seems to have been solved. Searching on the 'net, not being a mathematician myself, I came across the Dijkstra Algorithm. Is there anyone of you who has successfully used this algorithm in a Maps-like app in the iPhone? Would you be willing to share it with me/the community? Would this be the right approach, or are the other options? Thank you so much for your consideration.

Answer 1

Dijkstra's algorithm is for finding the shortest path to all nodes (from a single starting node). Game programmers use a directed search such as A*. Where Dijkstra processes the node that is closest to the starting position first, A* processes the one that is estimated to be nearest to the end position

The way this works is that you provide a cheap "estimate" function from any given position to the end point. A good example is how far a bird would fly to get there. A* adds this to the current distance from the start for each node and then chooses the node that seems to be on the shortest path.

The better your estimate, the shorter the time it will take to find a good path. If this time is still too long, you can do a path find on a simple map and then another on a more complex map to find the route between the places you found on the simple map.

Update After much searching, I have found an article on A* for you to to read

Answer 2

I do not believe Dijkstra's algorithm would be useful for real-world mapping because, as Tom Leys said (I would comment on his post, but lack the rep to do so), it requires a single starting point. If the starting point changes, everything must be recalculated, and I would imagine this would be quite slow on a device like the iPhone for a significantly large data set.

I could be wrong, though.

Answer 3

Dijkstra's algorithm is O(m log n) for n nodes and m edges (for a single path) and is efficient enough to be used for network routing. This means that it's efficient enough to be used for a one-off computation.

Briefly, Dijkstra's algorithm works like:

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 an all-pairs shortest path calculator, although it can be adapted to do this.

You would have 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 compute a shortest route.

Answer 4

This was discussed earlier here: What algorithms compute directions from point a to point b on a map?