3
$\begingroup$

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?

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

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

| improve this answer | |
$\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.