network/edmonds_karp library

🚀 Edmonds-Karp Algorithm (Improved Maximum Flow)

An optimized version of Ford-Fulkerson that uses breadth-first search (BFS) to find shortest augmenting paths, ensuring polynomial time complexity.

  • Time Complexity: O(VE²) where V is vertices, E is edges
  • Space Complexity: O(V²) for residual graph storage
  • Optimality: Guaranteed to find maximum flow
  • Completeness: Always terminates in polynomial time
  • Advantage: BFS ensures shortest augmenting paths, leading to fewer iterations

The algorithm improves upon Ford-Fulkerson by always selecting the shortest augmenting path, which guarantees polynomial time complexity and better performance in practice.

Example:

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

Classes

EdmondsKarpEdge<T>
Represents a flow network edge with capacity and flow
EdmondsKarpResult<T>
Edmonds-Karp with detailed flow information and path analysis

Functions

edmondsKarp<T>(Map<T, Map<T, num>> graph, T source, T sink) → num
Edmonds-Karp maximum flow algorithm implementation
edmondsKarpDetailed<T>(Map<T, Map<T, num>> graph, T source, T sink) → EdmondsKarpResult<T>
min<T extends num>(T a, T b) → T
Utility function for finding minimum of two numbers