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.
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

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

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