Let S be the set of all possible s-t shortest paths in a directed graph. A path s in S is said to be maximal if it is not a subpath of another path in S. Let M be the set of all maximal paths in S.
Does anyone know how to efficiently sample paths from M. Ideally, I would like the probability of sampling the longer paths in M to be higher.
Do you have a way to change from one path to another? If so, perhaps you could set up a markov chain and show that it mixes rapidly?
Another question: is it easy to determine the set of pairs which can serve as endpoints for such paths? For example, in the complete graph, all such paths have length 1, and any pair of vertices work: by contrast, in a cycle, only vertices halfway around the cycle from each other can be the endpoints of such paths.
Using a markov chain is an interesting approach however I currently do not have way to locally change one shortest path to another.
The idea of using the endpoints seems more suitable to the current project. The graphs we are looking at are derived from a road network, thus using your idea, I can choose endpoints from opposite ends of the graph (maybe using zipcodes or something similar). They won't necessarily be maximal but I think they should be long enough. Thanks!
One idea would be to generate all shortest paths using some Dijkstra-type algorithm, for all pairs a,b, and then, for all pairs a, b, look at all neighbours of a and see whether the shortest path is contained in a shortest path from a neighbour to b. Should be some way of doing this reasonably efficiently.
Sure, definitely will be emailing you soon! I like the idea of looking at all the neighbors and determining whether a shortest path is contained another shortest path. Since the graphs we're looking at have unique shortest paths, this makes it easier to do this.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs