Enumerate all paths in a weighted graph from A to B where path length is between C1 and C2

Posted by awmross on Stack Overflow See other posts from Stack Overflow or by awmross
Published on 2011-02-20T23:22:23Z Indexed on 2011/02/20 23:25 UTC
Read the original article Hit count: 291

Filed under:
|

Given two points A and B in a weighted graph, find all paths from A to B where the length of the path is between C1 and C2.

Ideally, each vertex should only be visited once, although this is not a hard requirement. I supose I could use a heuristic to sort the results of the algorithm to weed out "silly" paths (e.g. a path that just visits the same two nodes over and over again)

I can think of simple brute force algorithms, but are there any more sophisticed algorithms that will make this more efficient? I can imagine as the graph grows this could become expensive.

In the application I am developing, A & B are actually the same point (i.e. the path must return to the start), if that makes any difference.

Note that this is an engineering problem, not a computer science problem, so I can use an algorithm that is fast but not necessarily 100% accurate. i.e. it is ok if it returns most of the possible paths, or if most of the paths returned are within the given length range.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about graph