Package com.jgalgo

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.

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.Result	A result object for an ShortestPathAllPairs algorithm.

Method Summary

Modifier and Type	Method	Description
default ShortestPathAllPairs.Result	computeAllCardinalityShortestPaths(Graph g)	Compute the cardinality shortest path between each pair of vertices in a graph.
ShortestPathAllPairs.Result	computeAllShortestPaths(Graph g, WeightFunction w)	Compute the shortest path between each pair of vertices in a graph.
default ShortestPathAllPairs.Result	computeSubsetCardinalityShortestPaths(Graph g, IntCollection verticesSubset)	Compute the cardinality shortest path between each pair of vertices in a given subset of the vertices of the graph.
ShortestPathAllPairs.Result	computeSubsetShortestPaths(Graph g, IntCollection verticesSubset, WeightFunction w)	Compute the shortest path between each pair of vertices in a given subset of the vertices of the graph.
static ShortestPathAllPairs.Builder	newBuilder()	Create a new all pairs shortest paths algorithm builder.

Method Detail

computeAllShortestPaths

ShortestPathAllPairs.Result computeAllShortestPaths(Graph g,
                                                    WeightFunction 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.

Parameters:

g - a graph

w - an edge weight function

Returns:

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

computeSubsetShortestPaths

ShortestPathAllPairs.Result computeSubsetShortestPaths(Graph g,
                                                       IntCollection verticesSubset,
                                                       WeightFunction w)

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

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

computeAllCardinalityShortestPaths

default ShortestPathAllPairs.Result computeAllCardinalityShortestPaths(Graph g)

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

The cardinality length of a path is the number of edges in it. The cardinality shortest path from a source vertex to some other vertex is the path with the minimum number of edges.

Parameters:

g - a graph

Returns:

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

computeSubsetCardinalityShortestPaths

default ShortestPathAllPairs.Result computeSubsetCardinalityShortestPaths(Graph g,
                                                                          IntCollection verticesSubset)

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

The cardinality length of a path is the number of edges in it. The cardinality shortest path from a source vertex to some other vertex is the path with the minimum number of edges.

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

Returns:

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

newBuilder

static ShortestPathAllPairs.Builder newBuilder()

Create a new all pairs shortest paths algorithm builder.

This is the recommended way to instantiate a new ShortestPathAllPairs object.

Returns:

a new builder that can build ShortestPathAllPairs objects