Calculator Input
Example Data Table
Use this sample network to test the calculator.
| From | To | Capacity |
|---|---|---|
| S | A | 10 |
| S | C | 10 |
| A | B | 4 |
| A | C | 2 |
| A | D | 8 |
| C | D | 9 |
| D | B | 6 |
| B | T | 10 |
| D | T | 10 |
Formula Used
The Edmond Karp method solves the maximum flow problem by repeatedly finding the shortest augmenting path in the residual network.
Residual capacity: residual(u, v) = capacity(u, v) - flow(u, v)
Bottleneck value: min residual capacity on the selected augmenting path.
Flow update: flow(u, v) = flow(u, v) + bottleneck
Reverse update: flow(v, u) = flow(v, u) - bottleneck
Maximum flow: sum of all accepted bottleneck values.
The algorithm stops when breadth first search cannot reach the sink through positive residual capacity.
How to Use This Calculator
- Enter the source node name.
- Enter the sink node name.
- Add each directed edge on a new line.
- Write every edge as from,to,capacity.
- Press the calculate button.
- Review the maximum flow and augmenting paths.
- Check the residual capacity table.
- Download CSV or PDF reports when needed.
Understanding the Edmond Karp Algorithm
What the Method Solves
The Edmond Karp algorithm finds the greatest possible flow through a directed network. A network contains nodes, edges, capacities, a source, and a sink. Each edge limits how much flow can pass through it. The goal is to move as much flow as possible from the source to the sink. This calculator turns that process into a clear table. It shows each path used by the method. It also shows the bottleneck capacity on every path.
Why Breadth First Search Matters
The method is a special version of Ford Fulkerson. It always chooses an augmenting path found by breadth first search. That means it selects a path with the fewest edges first. This rule makes the process more predictable. It also gives the method a known polynomial running time. Each search checks the residual network. The residual network shows remaining usable capacity. It also includes reverse edges from previous choices.
How Flow Is Improved
After a path is found, the calculator finds its bottleneck. The bottleneck is the smallest residual capacity on that path. That value is added to every forward edge in the path. The same value is subtracted from reverse edges. This reverse adjustment is important. It lets later paths correct earlier flow choices. The running total increases after each successful augmentation.
Reading the Final Output
The maximum flow is the final total sent to the sink. The edge table displays original capacity, used flow, and remaining residual capacity. A full edge means its residual capacity is zero. The minimum cut section lists edges crossing from reachable nodes to unreachable nodes. Their total capacity should match the maximum flow. This result helps verify the answer. Use the CSV file for spreadsheets. Use the PDF report for notes, assignments, and documentation.
FAQs
What does this calculator find?
It finds the maximum possible flow from a chosen source node to a chosen sink node in a directed capacity network.
What input format should I use?
Enter one edge per line. Use the format from,to,capacity. For example, write S,A,10 for an edge from S to A.
Can capacities be decimal values?
Yes. The calculator accepts whole numbers and decimal capacities. Negative capacities are ignored because flow capacity cannot be negative.
Why does the method use breadth first search?
Breadth first search finds the shortest augmenting path by edge count. This choice makes the algorithm systematic and efficient.
What is a bottleneck?
The bottleneck is the smallest residual capacity on an augmenting path. It decides how much extra flow can be pushed.
What is residual capacity?
Residual capacity is unused capacity on an edge after current flow is considered. It guides the next possible augmenting path.
What is the minimum cut?
The minimum cut separates reachable nodes from unreachable nodes in the final residual graph. Its capacity equals the maximum flow.
Can I export the result?
Yes. Use the CSV button for spreadsheet data. Use the PDF button for a readable report of the displayed result.