Class ShortestPathSingleSourceGoldberg

  • All Implemented Interfaces:
    ShortestPathSingleSource

    public class ShortestPathSingleSourceGoldberg
    extends ShortestPathSingleSourceAbstract
    Goldberg's SSSP algorithm for integer (positive and negative) weights on directed graphs.

    The algorithm operate on integer weights and uses the scaling approach. During the scaling iterations, a potential function is maintained, which gives a equivalent weight function with values \(-1,0,1,2,3,\ldots\). The potential is updated from iteration to iteration, until the full representation of the integer numbers is used, and the real shortest paths and distances are computed. Let \(N\) be the absolute value of the minimum negative number. The algorithm perform \(O(\log N)\) iteration, and each iteration is performed in time \(O(m \sqrt{n})\) time. In total, the running time is \(O(m \sqrt{n} \log N)\).

    This algorithm is great in practice, and should be used for weights function with integer negative values.

    Based on 'Scaling algorithms for the shortest paths problem' by Goldberg, A.V. (1995).

    Author:
    Barak Ugav