- Maximum Flow Problem at Communications of the ACM :https://dl.acm.org/doi/10.1145/2628036

-[Network Flow Algorithms Starting Here](https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=33)

MIT Open Course Ware :

-13. Incremental Improvement: Max Flow, Min Cut](https://www.youtube.com/watch?v=VYZGlgzr_As)

- Actual Complexity of Max Flow Algorithmshttps://codeforces.com/blog/entry/52714

return solveWithFordFulkerson(transform(entrances, exits, path));

}

}

Ford-Fulkerson - Time Complexity: O(fV^2), where f is the max flow

The idea of Edmonds-Karp is to use BFS in Ford-Fulkerson

implementation as BFS always picks a path with minimum

number of edges. When BFS is used, the worst case time

complexity can be reduced to O(VE^2).

Time Complexity: O(EV²)

From further research, a more efficient algorithm - Dinic's algorithm selected.

The implementation was slightly modified as my implementation.

Further optimization of implemented Dinic's algorithm and also finding better

version is in progress.

Push-Relabel Maximum Flow Algorithm

Push-Relabel approach is the more efficient than Ford-Fulkerson algorithm. In this post, Goldberg’s “generic” maximum-flow algorithm is discussed that runs in O(V^2E) time. This time complexity is better than O(E^2V) which is time complexity of Edmond-Karp algorithm (a BFS based implementation of Ford-Fulkerson). There exist a push-relabel approach based algorithm that works in O(V3) which is even better than the one discussed here.

Similarities with Ford Fulkerson

Like Ford-Fulkerson, Push-Relabel also works on Residual Graph (Residual Graph of a flow network is a graph which indicates additional possible flow. If there is a path from source to sink in residual graph, then it is possible to add flow).

Differences with Ford Fulkerson

Push-relabel algorithm works in a more localized. Rather than examining the entire residual network to find an augmenting path, push-relabel algorithms work on one vertex at a time (Source : CLRS Book).

In Ford-Fulkerson, net difference between total outflow and total inflow for every vertex (Except source and sink) is maintained 0. Push-Relabel algorithm allows inflow to exceed the outflow before reaching the final flow. In final flow, the net difference is 0 for all except source and sink.

Time complexity wise more efficient.

Dinic's algorithm can be improved to O(VElogV) with dynamic trees.

There exists another more efficient algorithm James B Orlin's + KRT (King, Rao, Tarjan)'s algorithm to O(VE).

Amortized Analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic. - Wikipedia

Amortization

In computer science, amortised analysis is a method of analyzing the execution cost of algorithms over a sequence of operations. In the context of zoning regulations, amortisation refers to the time period a non-conforming property has to conform to a new zoning classification before the non-conforming use becomes prohibited. - Wikipedia

Amortization

A technique from financial analysis, but we've appropriated it in computer science as an analysis technique to say, well, let's not worry about every single operation worst case cost, let's just worry about the total operation, the sum of all the operations cost. -https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-videos/lecture-5-amortization-amortized-analysis

This lecture is about a cool data structure for maintaining rooted trees (potentially very unbalanced) in O(log n) time per operation. The operations include linking two trees together by adding an edge, and cutting an edge to split a tree into two trees, so the data structure is called link-cut trees. This result is our first solving a dynamic graph problem (where in general we can insert and delete edges); next lecture will see other solutions for trees and generalization from trees to undirected graphs. Link-cut trees have specific advantages in that they can represent information over root-to-node paths; for example, they can easily compute the min/max/sum of values stored in nodes or edges along any root-to-node paths. Most importantly, link-cut trees introduce two powerful tree decompositions: preferred-path decomposition (which we already used in Tango trees) and heavy-light decomposition. As we will cover them, link-cut trees also demonstrate how a surprisingly “care-free” use of splay trees is actually still efficient.

Goldberg and Tarjan O(nm log(n*/m)))

CSE 542. Advanced Data Structures and Algorithms Spring 2013https://www.arl.wustl.edu/~jst/cse/542/

Other solutions was not implmented due to time limitation.

publicNetworkFlowBase(int[]entrances,int[]exits,int[][]path ) {

MAX_VAL =20000;

this.path =path;

intcap =edge.remainingCapacity();

if (cap >0 && (level[edge.to] ==level[at] +1 )) {

intbottleNeck =dfs(edge.to,next,flow>cap ?cap :flow);

intbottleNeck =dfs(edge.to,next,flow );

if (bottleNeck >0 ) {

edge.augment(bottleNeck);