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.

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

2 Answers 2

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

$\endgroup$
7
  • $\begingroup$ You can also try this: $\endgroup$
    – a06e
    Jan 20, 2013 at 1:42
  • $\begingroup$ RandomTreeWeighted[n_, opts:OptionsPattern[]] := RandomTree[n, EdgeWeight -> RandomReal[{-1, 1}, n - 1], opts] $\endgroup$
    – a06e
    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
    Jan 20, 2013 at 1:44
  • $\begingroup$ It should work, because there are no cycles now. $\endgroup$
    – a06e
    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$ 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

$\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.