# How to find a path whose sum of weight is minimum when negative weights are present?

This question derive from How to find a longest path, which contains as many vertices,which is a solved problem.But I don't very happy with it based on a brute force method.So I try to built a negtive weight value since the documentation(ref/FindShortestPath-Examples-Scope-Specification) of FindShortestPath say:

The graph is

g=Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9,
10}, {SparseArray[Automatic, {10, 10},
0, {1, {{0, 2, 5, 7, 9, 11, 13, 15, 16, 18,
20}, {{3}, {4}, {1}, {6}, {8}, {5}, {9}, {2}, {9}, {2}, {6},
{3}, {5}, {7}, {8}, {4},
{1}, {8}, {1}, {3}}}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1}}], Null}, {VertexLabels -> {"Name"}}]


But this code get nothing:

FindShortestPath[
Graph[g, EdgeWeight -> Table[-1, EdgeCount[g]]], ##] & @@@
Tuples[Range[9], 2]


It's seem the FindShortestPath don't support the weight of negtive value.But as I know,the weight can be any value of real-number.Any method to do this by it or FindMinimumCostFlow in this answer?

• @Feyre The path's sum of weight is minimum?
– yode
Feb 4 '17 at 9:59
• I made a mistake. Feb 4 '17 at 10:02

I believe that the reason why FindShortestPath returns unevaluated is that your graph contains cycles. If there is a cycle with total negative weight, certain shortest paths will not exist. The path can always be made shorter (i.e. have a more negative total weight) by going around the cycle one more time.

Most, perhaps all, of the nodes in your graph are part of at least one cycle. Thus a shortest path having them as an endpoint does not exist (in the sense that for any path you choose there is always a shorter one—none of them are the shortest).