5
$\begingroup$

What is the best way to find a shortest path by using a custom distance function? I'm trying to play a little bit with the concept of using distributions instead of a deterministic weight value for each given edge. The results can be different, if we want, for example, to check what is the shortest path, with 95% "confidence". (The Flaw of Averages.) Our knowledge of the distances might not be a certainty and we may want to work with an interval or confidence range for the weights.

loc = Flatten[Solve[Mean[WeibullDistribution[2, 1, x]] == #, x] & /@ {1, 2, 3.01}];
{n1, n2, n3} = WeibullDistribution[2, 1, #] & /@ loc[[All, 2]];
network = {1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 5,
           2 \[UndirectedEdge] 3, 2 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 3,
           4 \[UndirectedEdge] 7, 4 \[UndirectedEdge] 6, 3 \[UndirectedEdge] 7,
           5 \[UndirectedEdge] 6, 6 \[UndirectedEdge] 7};
networkWeight = {n2, n3, n3, n2, n1, n1, n3, n2, n2, n2, n1};
edgeWeights = Map[Mean, networkWeight] // N;
edgeLabels = Thread[Rule[network, edgeWeights]];
g = Graph[network, EdgeWeight -> edgeWeights, EdgeLabels -> edgeLabels, 
VertexLabels -> "Name", VertexLabelStyle -> Directive[Red, Italic, 20], ImagePadding -> 20, 
GraphLayout -> "SpringEmbedding"]
FindShortestPath[g, 1, 7]

This will tell me that the shortest path from 1 to 7 is {1,2,3,7}.

But if I calculate the shortest path by hand using Monte Carlo,

   path147 = RandomVariate[n3, 10000] + RandomVariate[n3, 10000];
   path1237 =RandomVariate[n2, 10000] + RandomVariate[n2, 10000] + RandomVariate[n2, 10000];
   dist147 = EstimatedDistribution[path147, WeibullDistribution[α, β, μ]];
dist1237 = EstimatedDistribution[path1237, WeibullDistribution[α, β, μ]];
NSolve[CDF[dist1237, x] == 0.95 && x > 0, x, Reals] // Quiet
NSolve[CDF[dist147, x] == 0.95 && x > 0, x, Reals] // Quiet

we can see that the path {1,4,7} would be our choice in this case.

Is there a way to, after assigning the distribution to the EdgeWeight, to define a function that will calculate the total weight using the same concept shown above?

Many thanks.

$\endgroup$
  • $\begingroup$ Just a tiny note: NSolve[CDF[dist1237, x] == 0.95 && x > 0, x, Reals] is more tidily done as Quantile[dist1237, 0.95]. $\endgroup$ – J. M. is away Oct 14 '12 at 2:32
  • $\begingroup$ Maybe I'm reading something totally backwards here, but isn't the shortest pat 1-2-3-7? That sum is 2+2+2=6. The path you have is 1-4-7 which is 6.02, which is longer. It is late, I am tired, so I apologize for asking what is probably a silly or confused question. Maybe you could explain what is the output and how how you are interpreting it for the second block of code. This may help resolve the apparent contradiction. $\endgroup$ – Kellen Myers Aug 9 '14 at 5:24
  • $\begingroup$ Dear @KellenMyers. You've been duped by the "flaw of averages".hbr.org/2002/11/the-flaw-of-averages/ar/1 . Working with averages might make you take an incorrect decision. If instead of averages you work with Stochastic Variables, you would observe that the solution you would chose would be quite different. Some cartoons for your amusement (danielvaverka.com/the-flaw-of-averages) $\endgroup$ – Zviovich Aug 9 '14 at 5:49
  • $\begingroup$ Okay, but what I'm asking is in the first block of code, what is Mathematica doing wrong? Or is it that you have literally assigned the means to be the edge weights? Because that was the point of my comment. Mathematica is not making errors, right? I think that's what I'm trying to clear up. $\endgroup$ – Kellen Myers Aug 9 '14 at 6:34
  • $\begingroup$ Nevermind. Looking at this with some coffee shows me that this is exactly it -- I was interpreting the edge labels to be the edge weights. If anything, it's the "flaw of being enchanted by the pretty picture and overlooking what the code is saying." : ) $\endgroup$ – Kellen Myers Aug 12 '14 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.