Package com.jgalgo.alg.shortestpath

Class ShortestPathSingleSourceDial

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathSingleSourceAbstract

com.jgalgo.alg.shortestpath.ShortestPathSingleSourceDial

All Implemented Interfaces:

ShortestPathSingleSource

public class ShortestPathSingleSourceDial
extends ShortestPathSingleSourceAbstract

Dial's algorithm for Single Source Shortest Path for positive integer weights.

The algorithm runs in \(O(n + m + D)\) where \(D\) is the maximum distance, or the sum of heaviest n-1 edges if the maximum distance is not known. It takes advantage of the fact that a heap for integers can be implemented using buckets, one for each weight. Such a heap require \(D\) buckets, and therefore the algorithm running time and space depends on \(D\).

This algorithm should be used in case the maximal distance is known in advance, and its small. For example, its used by ShortestPathSingleSourceGoldberg as a subroutine, where the maximum distance is bounded by the number of layers.

Based on 'Algorithm 360: Shortest-Path Forest with Topological Ordering' by Dial, Robert B. (1969).

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
ShortestPathSingleSourceDial()	Create a Dial's SSSP algorithm for integer 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

ShortestPathSingleSourceDial

public ShortestPathSingleSourceDial()

Create a Dial's SSSP algorithm for integer weights.

Please prefer using ShortestPathSingleSource.newInstance() to get a default implementation for the ShortestPathSingleSource interface, or ShortestPathSingleSource.builder() for more customization options.