7
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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$? $\endgroup$
    – whuber
    Apr 15, 2013 at 13:59
  • $\begingroup$ Why don't you randomly change the edge lengths a bit? $\endgroup$
    – Sjoerd C. de Vries
    Apr 15, 2013 at 19:22
  • $\begingroup$ 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. $\endgroup$
    – Sjoerd C. de Vries
    Apr 16, 2013 at 12:36
  • $\begingroup$ @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. $\endgroup$
    – PinoAir
    Apr 16, 2013 at 12:38
  • $\begingroup$ One way to make an edge less likely to be (re)used is to increase its weight. $\endgroup$
    – Daniel Lichtblau
    Apr 17, 2013 at 18:14

1 Answer 1

Reset to default
0
$\begingroup$ 
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

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think this question might be a duplicate of this one... (not sure) $\endgroup$
    – rm -rf ♦
    Apr 17, 2013 at 15:00
  • $\begingroup$ @rm-rf Looks like it. I'll be voting to close. $\endgroup$
    – Sjoerd C. de Vries
    Apr 17, 2013 at 15:15

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