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.! –  PatoCriollo Oct 14 '12 at 12:55
add comment

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.