1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The usual definition of path is that you can't repeat vertices so, in a finite graph, there are only finitely many paths. Also, note that finding the longest path between two vertices is NP-hard so it's unlikely that you'll be able to efficiently collect a set of paths that spans most of the range from best to worst. $\endgroup$ – David Richerby Jun 11 '15 at 18:36
  • $\begingroup$ @DavidRicherby I would prefer if a solution would allow repetition of vertices, but I could live with one that doesn't. Also, I don't really want a collection of paths that span from best to worse. Just samples of path that span from best to say twice long as the ideal (my graph is very large, so twice as long is far from the worst). $\endgroup$ – asfsaf Jun 11 '15 at 18:38
  • $\begingroup$ ad 1): there are efficient algorithms that give you the k shortest paths; cf Eppstein. ad 2): that certainly gives you some paths. You may disconnect your target nodes, though, so you might have to backtrack. $\endgroup$ – Raphael Jun 12 '15 at 11:35
  • $\begingroup$ Please define what you are looking for more clearly. What do you mean by "the ideal path"? Do you mean the shortest path? When you talk about a path that is "close" to the ideal, how do you plan to measure "closeness"? Is it the difference between the length of that path minus the length of the ideal path? Or something else (like number of edges in common or something)? $\endgroup$ – D.W. Jun 14 '15 at 6:59
  • 1
    $\begingroup$ You can consider solutions of the following form: pick a random node C; now take the shortest path from A to C, and the shortest path from C to B. (After a precomputation that involves two runs of Dijkstra's algorithm -- i.e., to compute shortest-paths from A, and shortest-paths to B -- the A-C and C-B paths can be computed very efficiently.) You can choose C in a controlled way that controls the length of the resulting path. Is this the sort of thing that you're looking for? $\endgroup$ – D.W. Jun 14 '15 at 7:04
1
$\begingroup$

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.

  1. 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).

  2. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.