shortest distance through coordinates

Question

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. NO need to travel each and every point in the set. JUST THE POINTS THAT TAKE YOU TO POINT B and the distance covered in doing so should be minimum. ex: { (1,3),(1,4),(1,1),(5,2),(5,3),(1,4),(2,2),(1,2),(1,3)} and suppose A=(1,1) and B=(1,4) then the path={(1,1),(1,2),(1,3),(1,4)} note: paths need not be straight lines.can be zig zag too.

Answer 1

Since we can move at most two distance-units at a time, we can easily implement a DFS-traversal using sets and simply guessing whether points exist, since we have to guess for at most 8 points per point:

input: set points //a set of points that are placed on the grid
       point a
       point b
output: list path //a list of points, from a to b

map predecessor
predecessor.put(a , null)

set visited
visited.add(a)

//stores pairs consisting of (distance traveled , point)
//ordered ascending by distance to a
sortedset tovisit(sortyBy(pair::first , comparison::ascending)) 
tovisit.add(pair(0 , a))

//flag to check, if path was found
bool pathFound = false

while !tovisit.isEmpty()
    pair search = tovisit.remove(0)
    int dist = search.first()
    point pt = search.second()

    //check if we reached the end of the path
    if pt == b
        pathFound = true
        break

    //check if a point exists down from the current point
    //with a distance of at most 2 units that hasn't been visited
    point next = point(pt.x , pt.y + 1)
    if points.contains(next)
        if !visited.contains(next)
            predecessor.put(next , a)
            tovisit.add(pair(dist + 1 , next)
    else if points.contains(point(next.x , next.y + 1)
        next = point(pt.x , pt.y + 2)
        if !visited.contains(next)
            predecessor.put(next , a)
            tovisit.add(pair(dist + 2 , next)

    //proceed for other directions
    //...    

//build path
if !pathFound
    return null

list path
node tmp = b
do
    path.prepend(tmp)
    tmp = predecessor.get(tmp)
while tmp != null

return path

This code utilizes the fact, that we can only traverse at most 2 units in each direction, thus leaving us with at most 8 directions to check.

If this isn't given, we have to at first build a data-structure representing the grid. A simple solution would be to build a grid in which each point is connected to it's direct neighbors (worst case O(n ^ 2)) and traversing this grid with DFS.

Answer 2

Probably a more formal definition of "jumping across the points" is crucial to solve this problem. You may start with calculating distances for edges not violating the rule of not jumping. Next process the graph with Dijkstra algorithm or A*. Just first find how to mathematically identify valid edges.