All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Friends | List of all members
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
 

Additional Inherited Members

- 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
GThe graph.
sourceThe source node.
storePathsPaths are reconstructable and the number of paths is stored.
storeNodesSortedByDistanceStore a vector of nodes ordered in increasing distance from the source.
targetThe 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: