# FindShortestPath with negative weights isn't working

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.

-
The RandomTree function is from the documentation (up to minor variations). See the Applications section here –  becko Jan 19 '13 at 2:44
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

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.

-
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].

-