Package com.jgalgo.alg.shortestpath

Class ShortestPathSingleSourceDijkstra

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathSingleSourceAbstract

com.jgalgo.alg.shortestpath.ShortestPathSingleSourceDijkstra

All Implemented Interfaces:

ShortestPathSingleSource

public class ShortestPathSingleSourceDijkstra
extends ShortestPathSingleSourceAbstract

Dijkstra's algorithm for Single Source Shortest Path (SSSP).

Compute the shortest paths from a single source to all other vertices in \(O(m + n \log n)\) time, using a heap with \(O(1)\) time for decreaseKey() operations.

Only positive edge weights are supported. This implementation should be the first choice for ShortestPathSingleSource with positive weights. For negative weights use ShortestPathSingleSourceBellmanFord for floating points or ShortestPathSingleSourceGoldberg for integers.

Based on 'A note on two problems in connexion with graphs' by E. W. Dijkstra (1959). A 'note'??!! this guy changed the world, and he publish it as a 'note'.

Author:

Barak Ugav

See Also:

Wikipedia

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
ShortestPathSingleSourceDijkstra()	Create a Dijkstra's SSSP algorithm.

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 Detail

ShortestPathSingleSourceDijkstra

public ShortestPathSingleSourceDijkstra()

Create a Dijkstra's SSSP algorithm.

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