# 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
– a06e
Jan 19, 2013 at 2:44
• Seems the problem is with the negative weights. I tried BellmanFord to no avail Jan 19, 2013 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?
– a06e
Jan 19, 2013 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:
– a06e
Jan 20, 2013 at 1:42
• RandomTreeWeighted[n_, opts:OptionsPattern[]] := RandomTree[n, EdgeWeight -> RandomReal[{-1, 1}, n - 1], opts]
– a06e
Jan 20, 2013 at 1:43
• Then FindShortestPath[RandomTreeWeighted[10], 3, 7,Method -> "BellmanFord"] also returns unevaluated. Please tell me if you can reproduce this too.
– a06e
Jan 20, 2013 at 1:44
• It should work, because there are no cycles now.
– a06e
Jan 20, 2013 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 Jan 20, 2013 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].