Class SSSP¶

Inheritance Relationships¶

Class Documentation¶

class SSSP : public NetworKit::Algorithm¶

Abstract base class for single-source shortest path algorithms.

Subclassed by NetworKit::BFS, NetworKit::Dijkstra, NetworKit::DynSSSP, NetworKit::ReverseBFS

Public Functions

SSSP(const Graph &G, node source, bool storePaths = true, bool storeNodesSortedByDistance = false, node target = none)¶

Creates the SSSP class for G and source s.

Parameters:

• G – The graph.

• source – The source node.

• storePaths – Paths are reconstructable and the number of paths is stored.

• storeNodesSortedByDistance – Store a vector of nodes ordered in increasing distance from the source.

• target – The target node.

~SSSP() override = default¶

virtual void run() override = 0¶

Computes the shortest paths from the source to all other nodes.

const std::vector<edgeweight> &getDistances()¶

Returns a vector of weighted distances from the source node, i.e. the length of the shortest path from the source node to any other node.

Returns:

The weighted distances from the source node to any other node in the graph.

inline edgeweight distance(node t) const¶

Returns the distance from the source node to t.

Parameters:

t – Target node.

Returns:

The distance from source to target node t.

inline bigfloat numberOfPaths(node t) const¶

Returns the number of shortest paths between the source node and t.

Parameters:

t – Target node.

Returns:

The number of shortest paths between source and t.

inline double _numberOfPaths(node t) const¶

Returns the number of shortest paths between the source node and t as a double value. Workaround for Cython

Parameters:

t – Target node.

Returns:

The number of shortest paths between source and t.

inline const std::vector<node> &getPredecessors(node t) const¶

Returns the predecessor nodes of t on all shortest paths from source to t.

Parameters:

t – Target node.

Returns:

The predecessors of t on all shortest paths from source to t.

std::vector<node> getPath(node t, bool forward = true) const¶

Returns a shortest path from source to t and an empty path if source and t are not connected.

Parameters:

• t – Target node.

• forward – If true (default) the path is directed from source to t, otherwise the path is reversed.

Returns:

A shortest path from source to t or an empty path.

std::set<std::vector<node>> getPaths(node t, bool forward = true) const¶

Returns all shortest paths from source to t and an empty set if source and t are not connected.

Parameters:

• t – Target node.

• forward – If true (default) the path is directed from source to t, otherwise the path is reversed.

Returns:

All shortest paths from source node to target node t.

inline bigfloat getNumberOfPaths(node t) const¶

const std::vector<node> &getNodesSortedByDistance() const¶

Returns a vector of nodes ordered in increasing distance from the source.

For this functionality to be available, storeNodesSortedByDistance has to be set to true in the constructor. There are no guarantees regarding the ordering of two nodes with the same distance to the source.

Returns:

vector of nodes ordered in increasing distance from the source

inline count getReachableNodes() const¶

Returns the number of nodes reached by the source.

Returns:

Number of nodes reached by the source.

inline void setSource(node newSource)¶

Sets a new source.

Parameters:

newSource – The new source node.

inline void setTarget(node newTarget)¶

Sets a new target.

inline double getSumOfDistances() const¶

Returns the sum of distances from the source node node to the reached nodes.

Protected Attributes

const Graph *G¶

node source¶

node target¶

double sumDist¶

count reachedNodes¶

std::vector<edgeweight> distances¶

std::vector<std::vector<node>> previous¶

std::vector<bigfloat> npaths¶

std::vector<node> nodesSortedByDistance¶

bool storePaths¶

if true, paths are reconstructable and the number of paths is stored

bool storeNodesSortedByDistance¶

if true, store a vector of nodes ordered in increasing distance from the source