# | Likes | Tech tags | Title | Creator | Created date |
---|---|---|---|---|---|
1 | 0 |
2022-10-23 21:22
|
An \(O(F nm \log n)\) implementation of the successive shortest path algorithm (\(F\) is the maximum possible flow, \(n\) is the number of vertices, \(m\) is the number of edges). Uses Belleman-Ford derivative to compute the initial potentials and uses Dijkstra to find the shortest paths.
Caveat: The algorithm will fail if there is a negative cost cycle
#include<vector>
#include<deque>
#include<queue>
#include<limits>
#include<tuple>
#include<algorithm>
#include<iostream>
struct SuccessiveShortestPathFlowNetwork {
struct Arc {
int start_;
int end_;
int flow_;
int capacity_;
int cost_;
int get_dest(int from) { // Return the destination node if we were to traverse the arc from node `from`
if(from == start_) {
return end_;
} else {
return start_;
}
}
void add_flow(int from, int to_add) { // Adds flow from originating vertex `from`
if(from == start_) {
flow_ += to_add;
} else {
flow_ -= to_add;
}
}
int get_capacity(int from) { // Gets the capacity of the edge if the originating vertex is `from`
if(from == start_) {
return capacity_ - flow_;
} else {
return flow_;
}
}
int get_cost_from(int from) {
if(from == start_) {
return cost_;
} else {
return -cost_;
}
}
};
struct Node {
int index_;
std::vector<Arc*> connected_arcs_;
};
std::vector<Node> nodes_;
std::deque<Arc> arcs_;
void add_node() {
nodes_.push_back({int(nodes_.size()), {}});
}
int add_arc(int start, int end, int flow, int capacity, int cost) {
arcs_.push_back({start, end, flow, capacity, cost});
nodes_[start].connected_arcs_.push_back(&arcs_.back());
nodes_[end].connected_arcs_.push_back(&arcs_.back());
return (int)arcs_.size() - 1;
}
// Successive shortest paths min-cost max-flow algorithm
// If there is an negative cost cycle initially, then it goes into infinite loop
int min_cost_max_flow(int source_i, int sink_i) {
int result = 0;
// First calculate the potentials with Bellman–Ford derivative
// It starts from a single vertex and is optimized to only operate on active vertices on each layer
// Thus, it works more like a BFS derivative
std::vector<int> potentials(nodes_.size(), std::numeric_limits<int>::max());
{
std::deque<std::pair<int, int> > front;
front.push_back({0, source_i});
while(front.size() > 0) {
int potential;
int cur_i;
std::tie(potential, cur_i) = front.front();
front.pop_front();
if(potential >= potentials[cur_i]) {
continue;
}
potentials[cur_i] = potential;
for(Arc* arc : nodes_[cur_i].connected_arcs_) if(arc->get_capacity(cur_i) > 0) {
// Traverse the arc if there is some remaining capacity
front.push_back({potential + arc->get_cost_from(cur_i), arc->get_dest(cur_i)});
}
}
}
// Next loop Dijkstra to saturate flow. Once we subtract the difference in potential, every arc will have a
// non-negative cost in both directions, so using Dijkstra is safe
while(1) {
std::priority_queue<std::tuple<int, int, Arc*> > frontier;
std::vector<bool> explr(nodes_.size(), false);
std::vector<int> cost_to_node(nodes_.size(), -1);
std::vector<Arc*> arc_used(nodes_.size(), NULL);
frontier.push({0, source_i, NULL});
while(frontier.size() > 0) {
int path_cost;
int cur_i;
Arc* cur_arc_used;
std::tie(path_cost, cur_i, cur_arc_used) = frontier.top();
path_cost = -path_cost;
frontier.pop();
if(!explr[cur_i]) {
explr[cur_i] = true;
arc_used[cur_i] = cur_arc_used;
cost_to_node[cur_i] = path_cost;
for(Arc* arc : nodes_[cur_i].connected_arcs_) if(arc->get_capacity(cur_i) > 0) {
int next_i = arc->get_dest(cur_i);
// As priority_queue is a max-heap, we use the negative of the path cost for convenience
// We subtract the difference of potentials from the arc cost to ensure all arcs have positive
// cost
frontier.push({
-path_cost - (arc->get_cost_from(cur_i) - potentials[next_i] + potentials[cur_i]),
next_i,
arc
});
}
}
}
if(arc_used[sink_i] == NULL) {
return result; // We didn't find a path, so return
}
std::vector<Arc*> arcs;
int flow_pushed = std::numeric_limits<int>::max();
{
// Here we counstruct the path of arcs from source to sink
int cur_i = sink_i;
while(cur_i != source_i) {
Arc* arc = arc_used[cur_i];
cur_i = arc->get_dest(cur_i);
flow_pushed = std::min(flow_pushed, arc->get_capacity(cur_i));
arcs.push_back(arc);
}
// Next we push flow back across all the arcs
for(auto arc_it = arcs.rbegin(); arc_it != arcs.rend(); arc_it++) {
Arc* arc = *arc_it;
arc->add_flow(cur_i, flow_pushed);
result += arc->get_cost_from(cur_i) * flow_pushed;
cur_i = arc->get_dest(cur_i);
}
}
// Finally, update the potentials so all edge-traversal costs remain non-negative
for(int i=0; i<(int)nodes_.size(); i++) if(cost_to_node[i] != -1) {
potentials[i] += cost_to_node[i];
}
}
}
};
int main() {
SuccessiveShortestPathFlowNetwork graph;
for(int i=0; i<6; i++) graph.add_node(); // Initialize 6 nodes
// Add edges of our graph
graph.add_arc(0, 1, 0, 4, 1);
graph.add_arc(0, 3, 0, 2, 5);
graph.add_arc(1, 2, 0, 2, 1);
graph.add_arc(1, 3, 0, 6, 1);
graph.add_arc(2, 1, 0, 2, 1);
graph.add_arc(2, 5, 0, 4, 0);
graph.add_arc(3, 4, 0, 8, 1);
graph.add_arc(4, 2, 0, 6, -3);
graph.add_arc(4, 5, 0, 4, 1);
int result = graph.min_cost_max_flow(0, 5); // Find the min-cost max-flow
std::cout << result << '\n';
return 0;
}
Sample problem:
Minimum Cost Maximum Flow - hackerearth.com
Implement the successive shortest path algorithm for finding minimum cost max-flow. Construct a flow network and output the value of the min-cost max-flow on it.
Minimum Cost Flow Part Two: Successive Shortest Path Algorithm - topcoder.com
5.4 Successive Shortest Path Algorithm - Network flows: theory, algorithms, and applications (Ravindra Ahuja, Thomas Magnanti, James Orlin)
Flow network - wikipedia.org