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.
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, 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.
Why I need to do this: Essentially, in our "actual graph", each edge contains two weights. We want to find a path that maximizes the second weight, while being under the constraint that the path length in terms of the first weight does not violate a constraint (i.e. the path length isn't longer that 20% of the ideal path in terms of the first weight). It's impossible to solve non-heuristically in a reasonable amount of time, so we are essentially sampling a large number of random paths, eliminating those that violate the constraint and picking the best sample in terms of the second weight. We put a lot of time into this problem and this is the only solution that gives us anything close to a reasonable computation time