Class ShortestPathSingleSourceGoldberg
- All Implemented Interfaces:
ShortestPathSingleSource
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
ConstructorsConstructorDescriptionCreate a Goldberg's SSSP algorithm for integer weights, with negative weights. -
Method Summary
Methods inherited from class com.jgalgo.alg.shortestpath.ShortestPathSingleSourceAbstract
computeShortestPaths
-
Constructor Details
-
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 theShortestPathSingleSourceinterface, orShortestPathSingleSource.builder()for more customization options.
-