Faster parametric shortest path and minimum‐balance algorithms

We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm. For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O ( nm + n 2 log n ) time, improved from O ( nm log n ) for the parametric shortest path algorithm of Karp and Orlin and O ( n 2 m ) for the minimum‐balance algorithm of Schneider and Schneider. An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O ( n log n + m ).