# Making FindShortestPath a little bit sloppy [duplicate]

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?

• Your approach doesn't seem to match up to your wishes. If you want to "avoid some fraction $p$ ... [of] its previous solution," why not remove that fraction from the previous solution itself, rather than from all of $G$? – whuber Apr 15 '13 at 13:59
• Why don't you randomly change the edge lengths a bit? – Sjoerd C. de Vries Apr 15 '13 at 19:22
• I don't see how the "labeledness" is an issue here. It's not in your question at least and in the context of a shortest path it sounds strange. If you have a graph in which you want to find a shortest path then you need explicit distances between vertices, provided by for instance an adjacency matrix. You can multiply the distances in that matrix by a factor fluctuating around 1. The size of this fluctuation determines your sloppiness. – Sjoerd C. de Vries Apr 16 '13 at 12:36
• @SjoerdC.deVries Sorry, I misspoke - by "unlabeled" I meant that the graph has no edge weights assigned. I was asking for a fast method of assigned multiple sets of edge weights to the graph for each iteration of FindShortestPath. I like this solution a lot BTW, and I would be happy to accept it as an answer. – PinoAir Apr 16 '13 at 12:38
• One way to make an edge less likely to be (re)used is to increase its weight. – Daniel Lichtblau Apr 17 '13 at 18:14

SeedRandom;
n = 20;
p = 1.;
rm = RandomReal[{0, 5}, {n, n}];
rm = rm + rm\[Transpose];
(rm[[#, #]] = \[Infinity]) & /@ Range[n];
Do[{x, y} = RandomInteger[{1, n}, 2];
rm[[x, y]] = rm[[y, x]] = \[Infinity], {Floor[0.5 p n^2]}];
wag = WeightedAdjacencyGraph[rm, VertexLabels -> "Name",

HighlightGraph[wag, PathGraph@FindShortestPath[wag, 7, 17]] dm = RandomReal[{1 - \[Epsilon], 1 + \[Epsilon]}, {n, n}];
dm = (dm + dm\[Transpose])/2;
dwag = WeightedAdjacencyGraph[dm rm, VertexLabels -> "Name",  