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.

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.

share|improve this question
    
Just a tiny note: NSolve[CDF[dist1237, x] == 0.95 && x > 0, x, Reals] is more tidily done as Quantile[dist1237, 0.95]. –  J. M. Oct 14 '12 at 2:32
    
Thanks for the note J.M.! –  Zviovich Oct 14 '12 at 12:55
    
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. –  Kellen Myers Aug 9 at 5:24
    
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) –  Zviovich Aug 9 at 5:49
    
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. –  Kellen Myers Aug 9 at 6:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.