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.

Pejsach

Hold on. You want the shortest possible distance between two points that is not a vector that you have? Or just the shortest distance between two points? – Kauai

why not use the c++ standard library's std::shortest_path_between_points_in_electric_network_of_lines? – Dorice

@Cheersandhth.-Alf: Oh, come on. We all know that the current implementation of that stuff is still broken in all major compilers. – Hereabout

800 points should not be hard to brute force and get an answer in no time with the speed of modern computers. At each point, take minimum of all neighbors distance plus the distance to get to that node and stop when nothing changes (Dijkstra is a little more efficient). Don't worry about efficient algorithm for something this small. Initialize each point with infinity except the starting point, and set it to zero each round. – Elvinaelvira

@RobertRichter +1, early optimization is bad. Besides, coding a simple approach will likely make more complex approaches such as Dijkstra's algorithm easier to understand. – Ireful

Is there any documentation on how to use the Dijkstra Algorithm when the source points are given as X-Y coordinates in a single vector? or do I need to convert my source points to something else? Thanks @RobertRichter for your answer. – Pejsach

@ChristianLopez The method which you use to store your data shouldn't be relevant to the algorithm you use - it may change the resulting code but not the concept. Dijkstra's algorithm will require you to be able to find all points connected to the current point, and to measure the distance between any two points - if you are able to get this information out of your data structure then you are fine. – Ireful

Can it be assumed that each point can have a line connecting it to any other point? If so, at each point, get a distance from start. Initialize all points to infinity except the start. Something like this maybe with element 0 set to 0 (your starting point) for (i=1; i<Points; ++i) Distance[i]=infinity; for(i=1; i<Points; ++i) { for(j=0; j<Points; ++j) { if PointDistance(i, j)+Distance[j]<Distance[i] Distance[i]=PointDistance(i, j)+Distance[j]; } } – Elvinaelvira

In my last comment, If you are after lines (trenches) connecting the shortest path of points, then record which point (value of j) gave the shortest distance at each point (i), and you will have a trail you can go back on from end to start. – Elvinaelvira

@RobertRichter, There are approximately 310 lines, and each line can have up to 10 X-Y points that describe its path. I have saved this data in a vector size of 310, and each row at the same time contains the two single vectors, one for the X coordinates and another one for the Y coordinates. The issue is that the 310 lines are not stored graphically sequentially, meaning that for example line 0 is not in reality connected to line 1, but maybe to line 15. – Pejsach

Still use something similar to the loop as I described, and write a distance function, and if no line can be found to connect point I to J in your vector of 310, then return something indicating no path and therefore, you can't get a distance from that point. If a path can be found, let your distance function take the actual cost instead of "as the eagle flies (Pythagorean)". – Elvinaelvira

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?).

Marion

@paul123 yes paul, you are right, I have to work on my data structure so that each of the points are connected sequentially, one after the other. At this moment, that is not the situation. I have a vector size of 310 (310 lines) and each line has two single vectors X-Y coordinates that describe the path of each line. However, line 0 is not connected to line 1 but maybe to line 3 or 4. So I will first fix that on my vector so that each point connects to the previous and latter one. – Pejsach

Sounds like the first step is to somehow link up endpoints to something that stores information about the vertexes. Then simply iterate through the lines. For example, if endpoint 1 says "cost of 50" and endpoint 2 says "cost of 90), but the line says "cost of 6", then you would update endpoint 2 to be "cost of 56". If endpoint 1 says "cost of 90" and endpoint 2 says "cost of 40", then endpoint 1 would be updated to "cost of 46". If any endpoint changed, go again. – Elvinaelvira

(Comment too long, broken up) If each vertex records the line that was used to set a new minimum, then when the minimum distance stabilizes (nothing changes, so you are done), then you can work backwards from the end to the start to get the path. – Elvinaelvira

Beware of nasty bugs that can result from floating point optimization. Let's assume that you calculate the distance and due to rounding internally (extended precision in MPU and using the MPU cached value) you say "a new record has been reached", but when stored, it stores the same value as it had before, you can get in a loop that never exits. – Elvinaelvira

@Marion but how do i prepare my two dimensional vector containing the X-Y coordinates for the implementation of the shortest path search? Each line has a start x-y coordinate and also an end x-y coordinate. i do have more set of pair coordinates per line since the start-end is not always connected diagonally. I am lost on how to implement the algorithm... – Pejsach

Can you prepare an array of vertexes, and on each line, look at the start and endpoint, and see if there is already a vertex for it. If so, mark the endpoint as belonging to that vertex. If not, add a new vertex and then mark the endpoint. Do this for both endpoints. So, your lines should contain the following information: vertex index for endpoint 1, vertex index for endpoint 2, and the cost of the line (all its segments added together?). Each vertex should contain a cost to get there value and which line and endpoint resulted in the current value. – Elvinaelvira

Answer 2

For computing the shortest path Dijakstra would be fine.

You may get faster results from using A*, which uses a best guess of the distance in order to focus its search in the right direction, thereby getting there quicker.

If you are repeatedly querying the same data set, then memoization is fine.

Those people who recommend a brute-force algorithm are fools - it's worth taking a little time to learn how to program an efficient solution. But you could calculate the shortest path between all points using the Floyd-Warshall algorithm. Unfortunately, this won't tell you what the shortest path is just how long it is.

Adria

Answer 3

Just calculate the distance for all possible paths and pick the shortest one. 800 paths is nothing for modern PC. You will not even notice it.

Aruba

If you aren't careful and naively use recursion to find the path, it will break down exponentially, and 2^800 can be a VERY long time. – Elvinaelvira

For each permutation of 800 segments, check if it leads from A to B. If so, record path and distance, keeping the shortest one found so far. – Zoroastrian

Oh. I misunderstood his question. – Aruba