spacyc

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

SPACYC - acyclic shortest paths problem generator.

REMARK: Read SPRAND generator description first.

USAGE

  spacyc  n  m  seed  [ optional parameters ]

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


DESCRIPTION

  SPACYC generates acyclic network such that all nodes can be reached 
  from the source node (id 1). To ensure this, we generate one or more 
  special connecting paths. The other arcs are generated by choosing 
  two distinct nodes independently at random and making the node with 
  smaller id the tail and the other node the head of the arc.

  All parameters are the same as for SPRAND. The only difference is that 
  all parameters corresponding to connecting cycles in random networks
  correspond to the connecting paths in acyclic networks. The arc lengths
  are generated the same way as in SPRAND.

  The remaining difference from SPRAND is in generation connecting paths.
  By default, a single connecting path is generated. It contains n-1
  arcs: (1, 2), (2, 3), ... , (n-1, n). The default length of an arc in 
  the connecting path is 1.

  One can change the  number of arcs in the connecting path and the
  length of arcs in the connecting path. We will describe only changing 
  number of arcs in connected path. Changing the connecting arc lengths
  is the same as in SPRAND.

  -ch<path-len>

  <path-len> is a positive integer. If <path-len> = k < n-1, then SPACYC
  generates more than one connecting path. The number of arcs in each of 
  them (except may be the last one) is k. So, we have the connecting arcs

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

  The default value of <path-len> is n-1.


GENERAL REMARKS

  Acyclic networks are a special case of shortest paths problem. A special
  algorithm can solve such a problem in linear time. Surprisingly, acyclic 
  networks with negative lengths are very difficult for many programs.
  Even acyclic networks with nonnegative arc length are difficult for some
  programs, especially if the multipliers are used in the length function
  generation (-ln or -ls options).

  As SPRAND, the acyclic generator does not guarantee the absence of very 
  long arcs and possible overflows if the parameter values are large.

OUTPUT

  The only difference in output file compared to SPRAND is that the name 
  of problem begins with two letters "ac" instead of "rd".