jaykay@ut-emx.UUCP (R.Jayakrishnan) (07/29/90)
I am new to this newsgroup and I hope my following request-article is
not totally inappropriate here..
I am looking for an algorithm for k-shortest LOOPLESS paths from all
nodes to all nodes, in a network with directed arcs with non-integer
but positive costs, which could have cycles but (obviously) no
negative cycles.
The network is sparse (Arcs to nodes ratio= about 2 to 3, trip-times
on a street network is the actual problem).
I know of 1-to-all algorithms (Many versions of Dijkstra with heapsort,
Fibonacci sort, bucket sort, loose-end table sort etc..
Label correcting algorithms and Glover-Klingman's partitioning
algorithms), shortest paths. For all-to-all, we can repeat this or
use Floyd's or Dantzig's algorithms, both approaches being of the same
computational worst case of O(N**3), eventhough the Dijkstra with good
sorting can be done in O(N**2*logN). Recently Ahuja et al (Jl.of ACM
Vol.37,#2,1990) have proposed better worst case bounds for certain cases
with R-heaps, Radix sorts etc. It is straightforward to extend these
algorithms to the k-shortest paths, but there could be LOOPS in
the second to the k-th paths.
I know of one-to-one algorithms for loopless k-shortest paths (Yen's
algorithm and a few others).
I am pretty sure there are no algorithms for all-to-all loopless k-SP.
Is there at least a 1-to-all loopless k-SP algorithm, that can be
repeated ? Any suggestions for sensible modifications on Dijkstra-
like 1-to-all algorithms to prevent loops (short of looking back the
tree and checking for repeated nodes and thus adding an additional
N to the worst case) ?
(I am hoping to do it for a 500 node network, on a CRAY XMP-24. Any
thoughts on computation times ?)
Thanks in advance for any suggestions. I have been loosing a lot
of sleep over this, off late. Please help me out ! :-))
J.K. R. Jayakrishnan Dept. of Civil Engineering,
Univ. of Texas, Austin.
jaykay@emx.utexas.edu