Package com.jgalgo.alg.shortestpath

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.

Method Summary

Methods inherited from class com.jgalgo.alg.shortestpath.ShortestPathSingleSourceAbstract

computeShortestPaths

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 the ShortestPathSingleSource interface, or ShortestPathSingleSource.builder() for more customization options.