4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ The RandomTree function is from the documentation (up to minor variations). See the Applications section here $\endgroup$
    – a06e
    Commented Jan 19, 2013 at 2:44
  • 1
    $\begingroup$ Seems the problem is with the negative weights. I tried BellmanFord to no avail $\endgroup$
    – Dr. belisarius
    Commented Jan 19, 2013 at 2:48
  • $\begingroup$ @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? $\endgroup$
    – a06e
    Commented Jan 19, 2013 at 2:53

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ You can also try this: $\endgroup$
    – a06e
    Commented Jan 20, 2013 at 1:42
  • $\begingroup$ RandomTreeWeighted[n_, opts:OptionsPattern[]] := RandomTree[n, EdgeWeight -> RandomReal[{-1, 1}, n - 1], opts] $\endgroup$
    – a06e
    Commented Jan 20, 2013 at 1:43
  • $\begingroup$ Then FindShortestPath[RandomTreeWeighted[10], 3, 7,Method -> "BellmanFord"] also returns unevaluated. Please tell me if you can reproduce this too. $\endgroup$
    – a06e
    Commented Jan 20, 2013 at 1:44
  • $\begingroup$ It should work, because there are no cycles now. $\endgroup$
    – a06e
    Commented Jan 20, 2013 at 1:45
  • $\begingroup$ @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 $\endgroup$
    – Dr. belisarius
    Commented Jan 20, 2013 at 3:24
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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