Class ShortestPathSingleSourceGoldberg
- java.lang.Object
-
- com.jgalgo.alg.shortestpath.ShortestPathSingleSourceAbstract
-
- com.jgalgo.alg.shortestpath.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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface com.jgalgo.alg.shortestpath.ShortestPathSingleSource
ShortestPathSingleSource.Builder, ShortestPathSingleSource.IResult, ShortestPathSingleSource.Result<V,E>
-
-
Constructor Summary
Constructors Constructor Description ShortestPathSingleSourceGoldberg()
Create a Goldberg's SSSP algorithm for integer weights, with negative weights.
-
-
-
Constructor Detail
-
ShortestPathSingleSourceGoldberg
public ShortestPathSingleSourceGoldberg()
Create a Goldberg's SSSP algorithm for integer weights, with negative weights.Please prefer using
ShortestPathSingleSource.newInstance()
to get a default implementation for theShortestPathSingleSource
interface, orShortestPathSingleSource.builder()
for more customization options.
-
-