Algorithm for finding the shortest path between geocoordinates

AStar works on the basis of straight lines, AFAIK.

In my case, we have geocoordinates and I can get the straight line distance between the waypoints. But I am wondering how approximate will that be? The actual distance "by road", which actually matters can be different.

Example. Assuming A and B are on the same plane, and will be equidistant from the goal point, if we consider a straight line between A and the goal point and, B and the goal point.

The distance 开发者_Python百科"by road" between A and the goal point may be greater or lesser than B. But because the AStar works on the basis of straight lines, it will return both the routes as the shortest.

Is that correct?

If yes, then which algo should be considered , if we want the results on the basis of actual distance in Km/m?

If no, then what's the point that I am missing?

By default, A-star operates on a graph with edges having non-negative weights. There is no constraint that the edges have to be straight lines. The thing that makes A-star different, than say Dijkstra's algorithm, is that it uses a heuristic in which nodes of the graph to search first. This heuristic is typically chosen to be Euclidean distance between nodes in the case of a graph embedded in Euclidean space, though there are other possibilities.

OK, since you asked me to post an answer….

Before you understand A*, you must first understand Dijkstra's algorithm. Given a graph (a set of nodes, and edges between nodes) and the (positive) "distance" of each edge (e.g. the road distance), Dijkstra's algorithm gives the shortest distance between a certain source node and each destination node. For instance, in your graph, the nodes may be road-intersections, the edges may be the roads, and the weight/distance you put on an edge may be the length of that road, or the time it takes to traverse it, or whatever.

Please understand: Dijkstra's algorithm always gives the correct distance according to the weights you have put on the edges. In fact, the graph need not even be embeddable in a plane, i.e., there may be no notion of "straight line distance" in the first place. It can be any arbitrary graph.

Now, A* can be thought of as a particular heuristic to speed up Dijkstra's algorithm. You can think of it as using a heuristic to decide the order in which to consider nodes in the graph.

Formally: you have a graph G, two nodes s and t in it, and you want to find the distance d(s,t) between s and t. (The distance is according to the graph, e.g. according to road distance in your example.) To find d(s,t), in A* you use a heuristic function h(x) which satisfies h(x) ≤ d(x,t). For instance (just one possibility), you can choose h(x) to be the straight line distance from x to t. The better h(x) is as an estimate of d(x,t), the faster the A* algorithm will run, but the choice of h affects only the speed, not the answer: it will always give the shortest distance according to d, not h.

So to find the road distance s to t, just set d(u,v) to be the road distance for every pair of nodes u and v with a road between them, run A*, and you'll find the d(s,t) you want.

You can model the situation with a weighted graph, where vertices are the points you consider, and the edges between them have the weights equal to the road distances between corresponding points. Then you can use, for example, Dijkstra's algorithm to find the shortest distance between points.

For example, if you have points A and B on a plane, and the road distance between them is equal to C, then in graph you will have vertices [A] and [B] and an edge of length C between them:

[A]---C---[B]