NetworKit::Dijkstra Class Reference

Dijkstra's SSSP algorithm. More...

`#include <Dijkstra.h>`

## Public Member Functions

Dijkstra (const Graph &G, node source, bool storePaths=true, bool storeNodesSortedByDistance=false, node target=none)
Creates the Dijkstra class for G and the source node source. More...

virtual void run ()
Performs the Dijkstra SSSP algorithm on the graph given in the constructor. More...

Public Member Functions inherited from NetworKit::SSSP
SSSP (const Graph &G, node source, bool storePaths=true, bool storeNodesSortedByDistance=false, node target=none)
Creates the SSSP class for G and source s. More...

virtual ~SSSP ()=default

virtual std::vector< edgeweightgetDistances (bool moveOut=true)
Returns a vector of weighted distances from the source node, i.e. More...

edgeweight distance (node t) const
Returns the distance from the source node to t. More...

bigfloat numberOfPaths (node t) const
Returns the number of shortest paths between the source node and t. More...

double _numberOfPaths (node t) const
Returns the number of shortest paths between the source node and t as a double value. More...

std::vector< nodegetPredecessors (node t) const
Returns the predecessor nodes of t on all shortest paths from source to t. More...

virtual std::vector< nodegetPath (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. More...

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

bigfloat getNumberOfPaths (node t) const

virtual std::vector< nodegetStack (bool moveOut=true)
Returns a vector of nodes ordered in increasing distance from the source. More...

virtual std::vector< nodegetNodesSortedByDistance (bool moveOut=true)
Returns a vector of nodes ordered in increasing distance from the source. More...

Public Member Functions inherited from NetworKit::Algorithm
Algorithm ()
Constructor to the algorithm base class. More...

virtual ~Algorithm ()=default
Virtual default destructor. More...

bool hasFinished () const
Indicates whether an algorithm has completed computation or not. More...

void assureFinished () const
Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...

virtual std::string toString () const
Returns a string with the algorithm's name and its parameters, if there are any. More...

virtual bool isParallel () const

## Friends

class DynDijkstra

class DynDijkstra2

Protected Attributes inherited from NetworKit::SSSP
const GraphG

const node source

node target

std::vector< edgeweightdistances

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

std::vector< bigfloatnpaths

std::vector< nodenodesSortedByDistance

bool storePaths
if true, paths are reconstructable and the number of paths is stored More...

bool storeNodesSortedByDistance
if true, store a vector of nodes ordered in increasing distance from the source More...

Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
A boolean variable indicating whether an algorithm has finished its computation or not. More...

## Detailed Description

Dijkstra's SSSP algorithm.

## Constructor & Destructor Documentation

 NetworKit::Dijkstra::Dijkstra ( const Graph & G, node source, bool storePaths = `true`, bool storeNodesSortedByDistance = `false`, node target = `none` )

Creates the Dijkstra class for G and the source node source.

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.

## Member Function Documentation

 void NetworKit::Dijkstra::run ( )
virtual

Performs the Dijkstra SSSP algorithm on the graph given in the constructor.

Implements NetworKit::SSSP.

## Friends And Related Function Documentation

 friend class DynDijkstra
friend
 friend class DynDijkstra2
friend

The documentation for this class was generated from the following files: