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.

I have the following functions defined:

RandomTree[n_, opts:OptionsPattern[]] := 
TreeGraph[UndirectedEdge[RandomInteger[{1,#}], # + 1] & /@ Range[1, n - 1], opts]

RandomCycleTree[n_, opts:OptionsPattern[]] := Module[{tree, e},
tree = RandomTree[n];
e = RandomChoice[EdgeList[GraphComplement[tree]]];
GraphUnion[tree, Graph[{e}], opts]]

RandomCycleTreeWeighted[n_, opts:OptionsPattern[]] := 
RandomCycleTree[n, EdgeWeight -> RandomReal[{-1, 1}, n], opts]

If I execute:

FindShortestPath[RandomCycleTreeWeighted[10, 
VertexLabels -> "Name", ImagePadding -> 10], 3, 7]

it returns unevaluated. Can anyone reproduce this and explain why it is happening?

Note: I am using Mathematica 9. I also tried executing this in Mathematica 8.0 and it also didn't work.

share|improve this question
    
The RandomTree function is from the documentation (up to minor variations). See the Applications section here –  becko Jan 19 '13 at 2:44
1  
Seems the problem is with the negative weights. I tried BellmanFord to no avail –  belisarius Jan 19 '13 at 2:48
    
@belisarius Yes. Putting EdgeWeight -> RandomReal[{0, 1}, n] works fine. Weird, since in the documentation it is claimed that the "BellmanFord" method option should support negative weights. Is this a bug? –  becko Jan 19 '13 at 2:53

2 Answers 2

up vote 4 down vote accepted

FindShortestPath works for your graphs with Method->"BellmanFord" but ... your graphs should be Directed.

Bellman-Ford's algo works for graphs with negative edge weights, but only if they are free of negative weight cycles. Think of it as if you could get a -Infinity path: if your graph is undirected, you can always get a -Infinity valued path by going again and again forth and back over the same edge.

Mathematica graphics

share|improve this answer
    
You can also try this: –  becko Jan 20 '13 at 1:42
    
RandomTreeWeighted[n_, opts:OptionsPattern[]] := RandomTree[n, EdgeWeight -> RandomReal[{-1, 1}, n - 1], opts] –  becko Jan 20 '13 at 1:43
    
Then FindShortestPath[RandomTreeWeighted[10], 3, 7,Method -> "BellmanFord"] also returns unevaluated. Please tell me if you can reproduce this too. –  becko Jan 20 '13 at 1:44
    
It should work, because there are no cycles now. –  becko Jan 20 '13 at 1:45
    
@becko No, probably I haven't explained it clearly. An undirected graph is never cycle-free because a->b->a is a cycle and is always possible –  belisarius Jan 20 '13 at 3:24

RandomCycleTreeWeighted may generate graphs with negative cycles, whose edge sum to a negative value, and there may not be a shortest path. See Wikipedia Bellman-Ford page [1].

[1] http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

share|improve this answer

Your Answer

 
discard

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

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