Simplest path between points

views:

111

answers:

+1 Q:

Simplest path between points

I have a list of points (x, y coordinates) and a list of connections between them. Examples:

Points A B C D E

Connections AB BC CE BD

  D E
  | |
A-B-C

Of course, there are many more points and connections than this...

What I need to do is find out the simplest path between some of these points. For example, if I wanted to go to A, C, and D, I'd want to use connections AB, BC, and BD.

Is there a way to compute this for any set of points I want to connect?

+2 A:

Since you don't indicate that there is any cost associated with the edges, a Breadth First Search is probably what you are looking for. It finds the shortest path from a given node to all other nodes (if any exist), I am assuming that is what you mean by 'simplest'.

MAK 2010-02-10 09:31:13

@Phil: Please reread the Graph traversal chapter from a good book (try CLRS). BFS is guaranteed to return the shortest path in an unweighted graph, but DFS just finds any path, not necessarily the shortest. Read the proof of this. Furthermore, in an unweighted graph, all edge costs are generally assumed to be 1. If all costs are 0, the concept of a 'shortest' path is meaningless (all paths have cost 0). But maybe your problem needs costs to be 0 for some reason, in which case you should edit your question and define exactly what you mean by 'simplest'.

MAK 2010-02-10 17:30:11

You are right. I made a mistake. I took out my answer and gave you +1.

Phil 2010-02-11 17:21:50

ansaurus

tags:

views:

answers:

Simplest path between points

related questions