Package com.jgalgo.alg.shortestpath

Class ShortestPathAllPairsJohnson

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathAllPairsAbstract

com.jgalgo.alg.shortestpath.ShortestPathAllPairsJohnson

All Implemented Interfaces:

ShortestPathAllPairs

public class ShortestPathAllPairsJohnson
extends ShortestPathAllPairsAbstract

Johnson's algorithm for all pairs shortest path.

Calculate the shortest path between each pair of vertices in a graph in \(O(n m + n^2 \log n)\) time using \(O(n^2)\) space. Negative weights are supported.

The algorithm is faster than using ShortestPathSingleSourceBellmanFord \(n\) times, as it uses ShortestPathSingleSourceBellmanFord once to compute a potential for each vertex, resulting in an equivalent positive weight function, allowing us to use ShortestPathSingleSourceDijkstra from each vertex as a source.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.shortestpath.ShortestPathAllPairs

ShortestPathAllPairs.Builder, ShortestPathAllPairs.IResult, ShortestPathAllPairs.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
ShortestPathAllPairsJohnson()	Create a APSP algorithm.

Method Summary

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

computeAllShortestPaths, computeSubsetShortestPaths

Methods inherited from class java.lang.Object

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

Constructor Details

ShortestPathAllPairsJohnson

public ShortestPathAllPairsJohnson()

Create a APSP algorithm.

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