Class SuccessiveShortestPathMinCostFlow¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class SuccessiveShortestPathMinCostFlow : public NetworKit::Algorithm¶

Public Functions

SuccessiveShortestPathMinCostFlow(const Graph &G, std::string_view capacityName, std::string_view supplyName)¶

Constructs a min-cost flow solver using the successive shortest path algorithm.

Initializes the solver on a given directed, weighted graph with edge capacities and node supply/demand attributes.

Parameters:

• G – Underlying graph (must be directed, weighted, and have indexed edges).

• capacityName – Name of the edge attribute holding non-negative capacity values.

• supplyName – Name of the node attribute holding supply/demand values.

Throws:

std::runtime_error – if:

• the graph is not directed,

• the graph is not weighted,

• the graph does not have indexed edges,

• the specified edge attribute (capacities) does not exist,

• the specified node attribute (supplies) does not exist,

• any edge capacity is negative,

• or the sum of all node supplies/demands is not zero.

virtual void run() override¶

Compute a minimum-cost feasible flow using the successive shortest path algorithm.

This method implements the classic Successive Shortest Path (SSP) algorithm:

• Initializes node potentials using Bellman–Ford to reweight edges (ensuring non-negative reduced costs).

• Iteratively selects a supply node with positive imbalance.

• Runs Dijkstra on the residual network (with reduced costs) to find the cheapest augmenting path to a reachable demand node.

• Augments as much flow as possible along that path (bounded by supply, demand, and residual capacities).

• Updates node potentials and node imbalances.

The process continues until all supplies are pushed to demands. At the end, the edge attribute FLOW contains the computed flow on each edge, and getTotalCost() can be used to retrieve the total cost.

Throws:

std::runtime_error – if:

• a negative-cost cycle is detected in the residual graph,

• or if there exists remaining supply/demand that cannot be routed to any demand/supply.

inline double getTotalCost() const¶

Returns the total cost of the computed minimum-cost flow.

Throws:

std::runtime_error – if called before run() has finished.

Returns:

Total flow cost as a double.

inline Graph::EdgeDoubleAttribute getFlow() const¶

Returns the flow values assigned to each edge.

The returned attribute maps every edge to the computed flow value. Flow values are always non-negative and do not exceed the specified capacity.

Throws:

std::runtime_error – if called before run() has finished.

Returns:

EdgeDoubleAttribute object with flow values per edge.