How to design an approximate path solution?

Question

Hello everyone. I am attempting to write (or expand on an existing) graph search algorithm that will let me find the path to get closest to destination node considering there is no guarantee that the nodes will be connected.

To provide a realistic application of this, let's say I need to get from Brampton, Ontario to Hamilton, Ontario. I know my possible options at my start point are Local transit, GO bus or Walking. I know that walking is the least desired way to get to my destination so I look at GO bus first. I know I can take GO to a point close to Hamilton, but at that point the GO bus turns and goes another direction at that closest point is at a place where I have no options (other than walk, but the algorithm would only consider walking for short distances otherwise it will consider the route not feasible)

Using this same example, if the algorithm were to find that I can get there a way that is longer but gets me closer to the destination node (or possible at the destination node) that would be a higher weighted path (The weightings don't matter so much while its searching, only when the results are delivered, it would list by which path was closest to the destination in ascending order). For example, one GO Bus may get me 3km from the destination node, while 3 public transit buses would get me 500m away

So my question is two fold: 1) What algorithm should I start with that does something similar 2) How would I programmaticly explain that it's ok if nodes don't connect so that it doesn't just jump from node A to node R. Would starting from the end and working backward accomplish this

Edit: I forgot to ask how to aim for the best approximate solution because especially with a large graph there will be possibly millions of solutions for this problem.

Thanks, Michael

Answer 1

Read up on the A* algorithm. It is a generalization of Dijkstra's shortest path algorithm, that allows you to specify a heuristic, which provides a lower bound for distances between two verteces. In your case, the heuristic function would simply return the Euclidean distance.

Run the algorithm and keep track of the vertex with the best characteristic value, which you somehow compute from the graph distance from source and Euclidean distance to target. The only tricky part is to determine when to terminate (unless you want to traverse the entire graph).

Answer 2

Sounds very much like a travelling salesman problem with additional node characteristics. Just be wary that this type of problem is NP Complete and your best bet would be to go with some sort of approximation algorithm.

Answer 3

Why can't you assume that all nodes are connected? In the real world, they normally are, i.e. you can always walk or call a taxi, etc.?

In this case, you could simply change your model the following way: You have one graph for each transportation method. The nodes that are at the same place are connected with edges of weight 0 (i.e. if you are dropped off by car at an airport or train station).

Then, label each vertex and edge with the transportation type and you can simply use existing routing algorithms. Oh, by the way: A* will not scale well to really big networks. To get something that software like Yahoo/Google/Microsoft Maps actually would use, have a look here. The work of this research group includes the winner of the DIMACS shortest path challenge.