Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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
2  
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
add comment

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

SeedRandom[31415];
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]]

Gives:

enter image description here

or

enter image description here

share|improve this answer
    
I think this question might be a duplicate of this one... (not sure) –  rm -rf 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
add comment

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