Summary - Network flow
- Algorithms course
- Expert
- Lesson 30/41
- 4 min
Print the max flow in a mini task.
Summary - Network flow
In this group we covered the foundations of network flow: flow network, Ford-Fulkerson, Edmonds-Karp, max-flow min-cut and bipartite matching.
Ford-Fulkerson and Edmonds-Karp find the max flow via augmenting paths. The max-flow min-cut theorem links this to a cut problem; bipartite matching is an application.
We will now revisit source capacity with a small task.
Practice source_capacity mini task
Write source_capacity(graph, source). Return the total capacity of edges leaving the source. Print 8 with print(source_capacity([('s','a',5), ('s','b',3), ('a','t',4)], 's')).
Starter code
def source_capacity(graph, source):
# Total capacity leaving the sourceSample solution
def source_capacity(graph, source):
# Total capacity leaving the source
total = 0
for u, v, c in graph:
if u == source:
total += c
return total
print(source_capacity([('s','a',5), ('s','b',3), ('a','t',4)], 's'))Expected output
8
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Which method does Edmonds-Karp use?
- DFS
- Greedy
- BFS Correct answer
- DP
Explanation: Edmonds-Karp uses BFS to find the shortest path.
2 maximum flow value
# max_flow = min_cut_capacity
# max_flow == ____# max_flow = min_cut_capacity
# max_flow == min_cutExplanation: Maximum flow equals the minimum cut.
3 Method-tool
| Term | Meaning |
|---|---|
Ford-Fulkerson |
DFS |
Edmonds-Karp |
BFS |
max-flow min-cut |
Theorem |
bipartite matching |
Application |