How to get samples of different paths? 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.
I can think of two approaches. Each generates a single sample at a time; any modifications to the graph are undone before generating the next sample.


Compute the shortest path, then remove r of the edges you take and generate the next-shorted path. This can be used to generate nCr samples, though many will coincide. For better quality, you probably want to also apply this to its own output: find the initial shortest path, remove 2 edges, find the intermediate shortest path, remove 2 edges, find the final shortest path. For a reasonably large graph, I would just calculate the edge(s) to remove at random in each step. Variant: instead of removing a single edge, remove both that edge and all other edges that go in/out of either vertex (I would consider the graph undirected for this step).
Randomize the weights as you pass them to A*. That is, when you advance from one node to the next, multiply that edge's weight by a number between 0.9 and 1.1 (probably with a Gaussian distribution actually). On rare occasions this might generate loops, especially if you widen the random range.