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$
  • $\begingroup$ The RandomTree function is from the documentation (up to minor variations). See the Applications section here $\endgroup$ – becko Jan 19 '13 at 2:44
  • 1
    $\begingroup$ Seems the problem is with the negative weights. I tried BellmanFord to no avail $\endgroup$ – Dr. belisarius Jan 19 '13 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$ – becko Jan 19 '13 at 2:53
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$
  • $\begingroup$ You can also try this: $\endgroup$ – becko Jan 20 '13 at 1:42
  • $\begingroup$ RandomTreeWeighted[n_, opts:OptionsPattern[]] := RandomTree[n, EdgeWeight -> RandomReal[{-1, 1}, n - 1], opts] $\endgroup$ – becko Jan 20 '13 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$ – becko Jan 20 '13 at 1:44
  • $\begingroup$ It should work, because there are no cycles now. $\endgroup$ – becko Jan 20 '13 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 Jan 20 '13 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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