Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed).
Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B.
I essentially want X samples of all these paths. I don't want these samples to be "too close" to the ideal path. Essentially, I want them relatively spread out over the space of solutions. I do want to include cyclic paths, which I know makes the set of possible paths infinite. Therefore, I want the paths to be relatively close to the ideal path, but still not too close. This is obviously a very vague, non-rigourous description of this aspect of the problem, which is why if possible, I would like to be able to specify some parameter that lets me control how close to the ideal my samples are.
These are the solutions I have thought of so far:
1) Use some kind of algorithm that gives me the X shortest paths. The problem with this is the samples are all too similar to the ideal path in terms of length.
2) Do the following:
a) Run A*/Dijikstra's to find the ideal path. b) Remove X% of the edges that form the ideal path. c) Run A*/Dijistra's again to find the second sample. The fact that a portion of the edges have been removed from the ideal path, should mean that this second sample should be quite different. d) Remove X% of the edges that form the second sample. e) Repeat.
The problem with this is that I'm worried that for a large number of samples (10000+), a very large number of edges will be removed, making the samples taken later on to be very different from the ideal path.
Does anyone have any ideas on how to better approach the problem?
The graph is quite big (100000+ nodes and edges). The algorithm's speed and performance is very important, however I can do a very large amount of preprocessing beforehand, if necessary.