Shortest Path distance between points given as X-Y coordinates

Question

I am currently working on a project that has a vector containing X and Y coordinates for approximately 800 points. These points represent an electric network of lines. My goal is to compute the shortest distance Path between a Point A and Point B that can be or can not be located along the path given by the vectors containing the X-Y coordinates of the electric lines.

I have read about the Dijkstra Algorithm but since i am not that much familiar with it, I am not sure if I should go in that direction. I will be very thankful if I can get any feedback or comments from you that can direct me to solve this matter.

Answer 1

Any pathfinding algorithm depends on paths, points are just meaningless. What you have now is a list of "waypoints". However you have not explained how those points connect. For example if any and every point is connected to each other point the shortest distance would simply be the pythagoral distance between A & B. - I'm also unsure what you mean by X-Y coordinates of electric lines, such a "line" would always have a start & end position?

So the first step is to add to each point not only the x,y coordinates, but also a list of connectable points.

Once you did this you can start using a pathfinding algorithm (In this case A* would seem better than Dijkstra's though). It would simply be a standard implementation with each "cost" the actual distance between a point. (And for A* the heuristic would be the pythagoral distance to the end point).

For a good tutorial about A* (and other algorithms) you should check Amit's pages

EDIT, in reply to the comments.

It seems the first step is to convert a set of line segments to "points". The way I would go through this is:

collection AllPoints {containing Location & LinksToOtherPoints}
for each Segment
    get start/end Point of Segment
    if Point.Location is not in allPoints
        add Point to AllPoints
    add the other Point of Segment to LinksToOtherPoints

You then have simply a list with all points & the connections between them. As you have to constantly search the allPoints collection I suggest storing that in a binary tree structure (sets?).