Shortest path through coordinates

问题:

I am given a set of point in the x-y plane ={(x1,y1),(x2,y2),.....(xn,yn)}

and I am given two points a(xa,ya) and b(xb,yb) and asked to find the set of points that cover the shortest path.

no connection between points are given. If I assume a connection to every other point.it will take a long time to compute these values for a weighted graph. Can someone tell me what reading I should do. what topic does this problem come under graph algorithms?!!(Is there any specific algorithm) I have been stuck on this for days. note: need to go through the points. cannot jump across the points.

回答1:

The Shortest path between two points in a plane is a straight line. so you could use the points to form the equation of line and check if the set of points satisfies your equation.

Equation of line: y - y1 = m(x - x1)

where, m = (y2-y1)/(x2-x1)