I have a dense graph, and I'd like to find multiple "almost shortest" paths from a source vertex, $v_s$, to a sink vertex, $v_s$, on an undirected graph $G$. How can I repeatedly run FindShortestPath
so that it avoids some fraction $p$ of the vertices (or edges) on the path provided by its previous solution?
Thought: Starting from an undirected graph, can we dynamically randomize the direction of the graph edges after each application of FindShortestPath
?
Whatever the best solution may be, $G$ is very large, so I'm hoping that the "surgery" for every iteration doesn't require too much overhead.
Actually, the more I think about it, the more I like the idea of generating $N$ copies of my graph with randomly directed edges. Can I modify an undirected graph to have randomly directed edges? Can I be even more clever and do this for only the edges that FindShortestPath
searches through?