cugraph.sssp

cugraph.sssp(G, source=None, method=None, directed=None, return_predecessors=None, unweighted=None, overwrite=None, indices=None, cutoff=None)

Compute the distance and predecessors for shortest paths from the specified source to all the vertices in the graph. The distances column will store the distance from the source to each vertex. The predecessors column will store each vertex’s predecessor in the shortest path. Vertices that are unreachable will have a distance of infinity denoted by the maximum value of the data type and the predecessor set as -1. The source vertex’s predecessor is also set to -1. Graphs with negative weight cycles are not supported. Unweighted graphs are also unsupported.

For finding shortest paths on an unweighted graph, use BFS instead.

Parameters:

graphcugraph.Graph, CuPy or SciPy sparse matrix Graph or

matrix object, which should contain the connectivity information. Edge weights, if present, should be single or double precision floating point values. The current implementation only supports weighted graphs.

sourceint

Index of the source vertex.

cutoffdouble, optional (default=None)

Maximum edge weight sum considered by the algorithm

Returns:

Return value type is based on the input type. If G is a cugraph.Graph,

returns:

cudf.DataFrame

df[‘vertex’]

vertex id

df[‘distance’]

gives the path distance from the starting vertex

df[‘predecessor’]

the vertex it was reached from

If G is a CuPy or SciPy matrix, returns:

a 2-tuple of CuPy ndarrays (if CuPy matrix input) or Numpy ndarrays (if SciPy matrix input) representing:

distance: cupy or numpy ndarray

ndarray of shortest distances between source and vertex.

predecessor: cupy or numpy ndarray

ndarray of predecessors of a vertex on the path from source, which can be used to reconstruct the shortest paths.

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> distances = cugraph.sssp(G, 0)
>>> distances
        distance  vertex  predecessor
...       ...     ...         ...
...       ...     ...         ...
...       ...     ...         ...