sprand

17个最短路径源代码。代码效率高

SPRAND - random shortest paths network generator.

  SPRAND generates strongly connected random network. Strong 
  connectivity is achieved by generating one or several connecting 
  cycles. If an arc does not belong to a connecting cycle we choose 
  its tail and head randomly.


USAGE

  sprand  n  m  seed  [ optional parameters ]

  n     - the number of nodes,
  m     - the number of arcs,
  seed  - an odd positive number for initialization of random number 
          generator.

  The number of arcs must be sufficient to produce the connecting cycles. 
  For example, with one connecting cycle m must be at least n. 

  First three parameters are positional.The optional parameters begin
  with "-".


  Every time the generator is invoked with identical parameters and 
  parameter values, it generates identical networks.


HELP OPTIONS

  sprand -h

  This invocation of SPRAND prints short help.


  sprand -hh

  This invocation of SPRAND prints long help.


THE SOURCE 

  Usually, the source node id is 1. The only case it is not true is if
  the network has an artificial source (see below).


CONNECTING CYCLES

  By default the single connected cycle is generated. It contains n
  arcs: (1, 2), (2, 3), ... , (n-1, n), (n, 1). The default is to pick
  <len> at random.

  One can change the number of arcs in the connecting cycles and the
  length of arcs in the connecting cycle. 

  -cl<len>

  <len>, an integer, is the length of all arcs in the
  connecting cycles. (If <len> is negative then the resulting problem
  will have a negative length cycle.)

  The default value of <len> is 1.

  -ch<cycle-len>

  The default value of <cycle-len> is n.

  <cycle-len> is an integer > 1. If <cycle-len> = k < n
  then SPRAND generates more than one connecting cycle. The number of 
  arcs in all of them (except possible the last one) is k. So, we have the 
  connecting cycle arcs:

  (1,2),...,(k-1,k), (k,1), (1,k+1),...,(2k-1,1),...,(1,j*(k-1)+2),...,(n,1)

  The connecting cycles guarantee strong connectivity. If the length of 
  the connecting cycle arcs is small then many of them are likely to be 
  in the shortest path tree. So, tree may be very high if we have one 
  connecting cycle. Such a problem may be difficult for some algorithms.
  Choosing short connecting cycles and small connecting arc length tends
  to yield a short tree, and some algorithms behave much better on these 
  problems.

  Connecting arcs with big length are unlikely to be in the shortest path 
  tree. In this case the height of such a tree is usually small.


RANDOM ARCS

  The tail and the head of a random arc are chosen independently at 
  random from the interval [1, n]. The length of a random arc is chosen 
  uniformly at random from the interval [<lower-bound>, <upper-bound>]. 
  The length may  be changed using <linear-multiplier> and 
  <square-multiplier>.

  -ll<upper-bound> - the upper bound on random arc length.
  -lm<lower-bound> - the lower bound on random arc length.

  Both the upper bound and lower bound must be integers between 
  -2^31 and 2^31-1. Setting these bounds too high may cause overflow
  of distance labels in shortest paths codes.

  If <upper-bound> is less than <lower-bound> then SPRAND swaps these 
  values. 

  The default value of <upper-bound> is 10000.
  The default value of <lower-bound> is 0.


  Linear and square multipliers can be used to produce problems which are
  harder for some algorithms. 

  -ln<linear-multiplier> - a real number.

  If linear multiplier is not zero then for any arc (i,j) with length 
  l(i,j) SPRAND adds l(i,j)*<linear-multiplier>*|j-i| to the length.

  -ls<square-multiplier> - a real number.

  If square multiplier is not zero then  for any arc (i,j) with length 
  l(i,j) SPRAND adds l(i,j)*<square-multiplier>*|j-i|^2 to the length. 

  Setting the multiplier values too big may cause overflows.

NODE POTENTIALS

  A simple way to generate a problem with negative arc lengths but without
  a negative cycle is to generate potentials. Potential of a node i is
  an integer P(i). If SPRAND generates a problem with potentials, it 
  modifies the length of arc (i,j) as follows:

  l(i,j) = l(i,j) + P(i) - P(j)


  The values of potentials are distributed uniformly between the 
  <lower-potential-bound> and the <upper-potential-bound>. These values
  can be modified with <linear-potential-multiplier> and
  <square-potential-multiplier>. Approximately
  <%-of-alternative-potentials> percents of nodes may get "alternative
  potential" - potential multiplied by <alternative-multiplier>.

  -p - generate problem with default values of potential parameters.
  -pl<upper-potential-bound> - an integer.
  -pm<lower-potential-bound> - an integer.

  The default value of <upper-potential-bound> is <upper-bound> an upper
  bound on arc length.
  The default value of <lower-potential-bound> is <lower-bound> a lower
  bound on arc length.

  -pn<linear-potential-multiplier> - an arbitrary real number.
  -ps<square-potential-multiplier> - an arbitrary real number.

  The default value of <linear-potential-multiplier> and
  <square-potential-multiplier> is zero.

  If linear multiplier is not zero then SPRAND adds
  <linear-potential-multiplier>*i to the potential P(i) of every node i.

  If square multiplier is not zero then SPRAND adds
  <square-potential-multiplier>*(i^2) to the potential P(i) of every node.

  Potentials make the problems harder for some algorithms. Alternative
  potentials may make problems even harder.

  -pap<%-of-alternative-potentials> - a positive integer between 0 and 100. 
  -pac<alternative-multiplier> - an arbitrary real number.

  If <%-of-alternative-potentials> is greater than zero then for 
  approximately <%-of-alternative-potentials> percent of nodes their 
  potentials are multiplied by <alternative-multiplier>:

  P(i) = P(i) * <alternative-multiplier>

  By default, <%-of-alternative-potentials> is equal to zero and
  <alternative-multiplier> is equal to -1.

  If two problems differ only in potential parameter values, the
  geometry of the networks is the same, and the lengths differ only
  by the potential transformation.


ARTIFICIAL SOURCE

  Adding an artificial source and artificial arcs to a network is a
  standard technique used in reductions. It is quite surprising that when 
  the artificial source is added, the problem becomes much harder for 
  some algorithms.

  -s - generate artificial source and artificial arcs with default lengths. 

  The artificial source id is n+1. Artificial arcs connect the artificial 
  source to all other node in the network. Hence, the number of
  nodes in network with artificial source is n+1 and the number of arcs
  is m+n. The length of the arc from the artificial source to the real 
  source is 0. The lengths of other artificial arcs are uniformly
  distributed between <artificial-lower-bound> and  
  <artificial-upper-bound> and are very long by default.

  -sl<artificial-upper-bound> - an integer.
  -sm<artificial-lower-bound> - an integer.

  By default, the <artificial-upper-bound> and 
  <artificial-lower-bound> are 10^8.


GENERAL REMARKS

  Random networks are widely used in testing optimization codes.
  Although these networks are far from geographical networks, they or
  similar ones may appear in some applications. They are in some sense 
  "simplest" networks and make a reasonable test case. These networks
  are not so simple for finding shortest paths as one may think because
  of the expansion property of random graphs.

  If the parameters are set so that the random arc length is selected
  from an interval containing negative numbers, negative length cycles
  become a possibility. If arc lengths are too big, they cause overflows
  when computing shortest paths. 


OUTPUT

  The output format is described in the "format" file. 

  The problem name includes generator identifier, number of nodes, number 
  of arcs, seed and possibly some additional information.

  If any connecting cycle parameters are used, then the name of the 
  problem contains additional letter "c". Options on arc lengths force 
  letter "l", on artificial source - "s", on potentials - "p". For 
  example, name of the problem with no optional parameters looks like 
  this: rd_100_500_287_. If all classes of optional parameters are used,
  then the name is rd_100_500_311_lcsp. Any subset of additional letters 
  may appear in the problem name.

  If no optional parameters are used, the problem name gives you full
  information about the problem. But if additional parameters are used,
  the name does not give the full information. In this case the full
  description is given by the comment lines at the beginning of the 
  file.