Package com.jgalgo.alg

Interface ShortestPathAllPairs

public interface ShortestPathAllPairs

An algorithm that compute all pairs shortest path (APSP) in a graph.

The regular ShortestPathSingleSource can be used \(n\) times to achieve the same result, but it may be more efficient to use a APSP algorithm in the first place.

Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	ShortestPathAllPairs.Builder	A builder for ShortestPathAllPairs objects.
static interface	ShortestPathAllPairs.IResult	A result object for an ShortestPathAllPairs algorithm for IntGraph.
static interface	ShortestPathAllPairs.Result<V,E>	A result object for an ShortestPathAllPairs algorithm.

Method Summary

Modifier and Type	Method	Description
static ShortestPathAllPairs.Builder	builder()	Create a new all pairs shortest paths algorithm builder.
<V,E> ShortestPathAllPairs.Result<V,E>	computeAllShortestPaths(Graph<V,E> g, WeightFunction<E> w)	Compute the shortest path between each pair of vertices in a graph.
<V,E> ShortestPathAllPairs.Result<V,E>	computeSubsetShortestPaths(Graph<V,E> g, Collection<V> verticesSubset, WeightFunction<E> w)	Compute the shortest path between each pair of vertices in a given subset of the vertices of the graph.
static ShortestPathAllPairs	newInstance()	Create a new all-pairs-shortest-paths algorithm object.

Method Detail

computeAllShortestPaths

<V,E> ShortestPathAllPairs.Result<V,E> computeAllShortestPaths(Graph<V,E> g,
                                                                           WeightFunction<E> w)

Compute the shortest path between each pair of vertices in a graph.

Given an edge weight function, the length of a path is the weight sum of all edges of the path. The shortest path from a source vertex to some other vertex is the path with the minimum weight.

To compute the shortest cardinality (non weighted) paths, pass null instead of the weight function w.

If g is an IntGraph, a ShortestPathAllPairs.IResult object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

Returns:

a result object containing information on the shortest path between each pair of vertices

Throws:

NegativeCycleException - if a negative cycle is detected in the graph

computeSubsetShortestPaths

<V,E> ShortestPathAllPairs.Result<V,E> computeSubsetShortestPaths(Graph<V,E> g,
                                                                              Collection<V> verticesSubset,
                                                                              WeightFunction<E> w)

Compute the shortest path between each pair of vertices in a given subset of the vertices of the graph.

To compute the shortest cardinality (non weighted) paths, pass null instead of the weight function w.

If g is an IntGraph, a ShortestPathAllPairs.IResult object will be returned. In that case, its better to pass a IWeightFunction as w and IntCollection as verticesSubset to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

verticesSubset - a subset of vertices of the graph. All shortest paths will be computed between each pair of vertices from the subset

w - as edge weight function

Returns:

a result object containing information on the shortest path between each pair of vertices in the subset

Throws:

NegativeCycleException - if a negative cycle is detected in the graph. If there is a negative cycle that is not reachable from the set of given vertices, it might not be detected, depending on the implementation

newInstance

static ShortestPathAllPairs newInstance()

Create a new all-pairs-shortest-paths algorithm object.

This is the recommended way to instantiate a new ShortestPathAllPairs object. The ShortestPathAllPairs.Builder might support different options to obtain different implementations.

Returns:

a default implementation of ShortestPathAllPairs

builder

static ShortestPathAllPairs.Builder builder()

Create a new all pairs shortest paths algorithm builder.

Use newInstance() for a default implementation.

Returns:

a new builder that can build ShortestPathAllPairs objects