Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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?

share|improve this question

marked as duplicate by Sjoerd C. de Vries, István Zachar, Oleksandr R., R. M. Apr 17 '13 at 20:49

This question was marked as an exact duplicate of an existing question.

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
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", 
   PlotRangePadding -> 0.1];

HighlightGraph[wag, PathGraph@FindShortestPath[wag, 7, 17]]

enter image description here

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


enter image description here


enter image description here

share|improve this answer
I think this question might be a duplicate of this one... (not sure) – R. M. Apr 17 '13 at 15:00
@rm-rf Looks like it. I'll be voting to close. – Sjoerd C. de Vries Apr 17 '13 at 15:15

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