Shortest Path distance between points given as X-Y

问题:

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.

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

回答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.

回答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.