Class IncompleteDijkstra¶

Inheritance Relationships¶

Class Documentation¶

class IncompleteDijkstra : public NetworKit::IncompleteSSSP¶

Implementation of IncompleteSSSP using a normal Dijkstra with binary heaps.

Public Functions

IncompleteDijkstra(const Graph *G, const std::vector<node> &sources, const std::unordered_set<node> *explored = nullptr)¶

Creates a IncompleteDijkstra instance from the sources in sources (act like a super source) in the graph G. The edges in G must have nonnegative weight and G should not be null.

We also consider the nodes in explored to not exist if explored is not null.

Todo:

This is somewhat ugly, but we do not want introduce a std::shared_ptr<> since G and explored could well be stack allocated.

Warning

We do not copy G or explored, but store a non-owning pointer to them. Otherwise IncompleteDijkstra would not be more efficient than normal Dijkstra. Thus, G and explored must exist at least as long as this IncompleteDijkstra instance.

virtual bool hasNext() override¶

Returns whether there is a next-nearest node or all of the nodes reachable from the source have already been processed.

virtual std::pair<node, edgeweight> next() override¶

Returns the next-nearest node from the source and its distance to the source. Should only be called if hasNext() returns true.