network/dinics_algorithm library

⚡ Dinic's Algorithm (High-Performance Maximum Flow)

A highly efficient maximum flow algorithm that uses layered networks and blocking flows to achieve superior performance for large networks.

  • Time Complexity: O(V²E) where V is vertices, E is edges
  • Space Complexity: O(V²) for layered network storage
  • Optimality: Guaranteed to find maximum flow
  • Completeness: Always terminates in polynomial time
  • Performance: Significantly faster than Ford-Fulkerson and Edmonds-Karp
  • Best For: Dense graphs and large networks

Dinic's algorithm works by building layered networks and finding blocking flows in each layer, which dramatically reduces the number of augmenting paths needed.

Example:

final graph = <String, Map<String, num>>{
  'S': {'A': 10, 'B': 10},
  'A': {'B': 2, 'T': 8},
  'B': {'T': 10},
  'T': {},
};
final maxFlow = dinicsAlgorithm(graph, 'S', 'T');
// Result: 18 (maximum flow from S to T)

Classes

DinicsEdge<T>
Represents a flow network edge with capacity and flow
DinicsResult<T>
Dinic's algorithm with detailed analysis and performance metrics
LayeredNode<T>
Represents a node in the layered network with its level

Functions

dinicsAlgorithm<T>(Map<T, Map<T, num>> graph, T source, T sink) → num
Dinic's maximum flow algorithm implementation
dinicsAlgorithmDetailed<T>(Map<T, Map<T, num>> graph, T source, T sink) → DinicsResult<T>
min<T extends num>(T a, T b) → T
Utility function for finding minimum of two numbers