--- title: Network Flows description: Network flows involve directing traffic through a network with capacity constraints. Learners will understand the Max-Flow Min-Cut theorem and apply algorithms to optimize transportation, logistics, and data routing problems. category: mathematics subcategory: graph-theory difficulty: beginner, intermediate, advanced url: /subject/network-flows --- # Network Flows Network flows involve directing traffic through a network with capacity constraints. Learners will understand the Max-Flow Min-Cut theorem and apply algorithms to optimize transportation, logistics, and data routing problems. ## Available Resources 2 Books • 4 Courses • 3 Websites • 1 Papers ## Websites ### 1. CP-Algorithms - Minimum-cost flow (successive shortest path) Article explaining the successive shortest path algorithm for minimum-cost flow, an extension of Edmonds-Karp that augments along cheapest paths, covering directed and undirected graphs, complexity analysis, an SPFA-based implementation, and practice problems. Readers can implement min-cost max-flow for contest problems. **Difficulty:** Advanced | **Price:** Free **Link:** https://cp-algorithms.com/graph/min_cost_flow.html **Tags:** min-cost-flow, network-flow, shortest-paths, graph-algorithms, competitive-programming ### 2. Maximum Flow: Ford-Fulkerson and Edmonds-Karp Implementation-focused reference maintained by the competitive programming community. Explains the Ford-Fulkerson method, residual capacities, the integral flow and max-flow min-cut theorems, with working C++ code. Linked sibling pages cover Dinic's algorithm, push-relabel, and minimum-cost flow. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://cp-algorithms.com/graph/edmonds_karp.html **Tags:** maximum-flow, ford-fulkerson, edmonds-karp, competitive-programming, graph-algorithms ### 3. Wolfram MathWorld **Author:** Eric W. Weisstein MathWorld is an online mathematics encyclopedia from Wolfram Research offering detailed, browsable articles on topics across the math spectrum, including algebra, geometry, calculus, and number theory. Each entry includes definitions, theorems, formulas, diagrams, worked examples, and links to further reading. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://mathworld.wolfram.com **Tags:** mathematics-reference, encyclopedia, abstract-algebra, number-theory, geometry ## Courses ### 1. Design and Analysis of Algorithms (MIT 6.046J) **Author:** Erik Demaine, Srini Devadas, Nancy Lynch Intermediate algorithms after 6.006: divide-and-conquer, randomization, dynamic programming, greedy algorithms, network flow, amortization, complexity and cryptography. 39 lecture videos, notes, problem sets and exams with solutions train learners to design efficient algorithms and prove their correctness and running time. **Difficulty:** Intermediate | **Price:** Free **Link:** https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/ **Tags:** algorithm-design, dynamic-programming, randomized-algorithms, greedy-algorithms, network-flow, complexity-analysis ### 2. CS261: A Second Course in Algorithms **Author:** Tim Roughgarden Stanford's second algorithms course, with free lecture videos and notes. Twenty lectures build from Ford-Fulkerson through Edmonds-Karp, Dinic's blocking flows, push-relabel, minimum s-t cut for image segmentation, bipartite and minimum-cost matching, then linear programming duality and strong duality. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://timroughgarden.org/w16/w16.html **Tags:** network-flows, push-relabel, bipartite-matching, linear-programming, lp-duality, algorithm-design ### 3. Routing Algorithms UC San Diego and HSE course on graph algorithms: graph representation, exploration and connectivity, topological sort, strongly connected components, shortest paths with BFS, Dijkstra, and Bellman-Ford, and minimum spanning trees. Learners implement each algorithm in programming assignments. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://www.coursera.org/learn/algorithms-on-graphs **Tags:** courses, technology-computer-science, computer-networks ### 4. Introduction to Graph Theory We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. In this online course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible! By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students. **Difficulty:** Beginner | **Language:** English | **Duration:** 5 weeks, 3-5 hours/week | **Price:** Free **Link:** https://www.coursera.org/learn/graphs **Tags:** courses, mathematics-statistics, combinatorics ## Youtubes ### 1. Lecture 13: Incremental Improvement: Max Flow, Min Cut (MIT 6.046J) **Author:** Srinivas Devadas Introduces flow networks, cuts, residual graphs and augmenting paths, proves the max-flow min-cut theorem, and develops the Ford-Fulkerson method and its running time. This single recorded lecture prepares learners to compute maximum flows and minimum cuts in directed graphs. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://www.youtube.com/watch?v=VYZGlgzr_As **Tags:** maximum-flow, minimum-cut, ford-fulkerson, residual-graphs, graph-algorithms ## Papers ### 1. Algorithms, Chapter 10: Maximum Flows & Minimum Cuts **Author:** Jeff Erickson Chapter from Erickson's Creative Commons algorithms textbook. Develops flows, cuts, residual graphs, and the max-flow min-cut theorem with careful proofs, then Ford-Fulkerson's non-termination on irrational capacities, Edmonds-Karp variants, and Dinic's algorithm. A companion chapter covers applications. **Difficulty:** Intermediate | **Language:** English | **Price:** Free **Link:** https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf **Tags:** maximum-flow, minimum-cut, residual-graphs, dinic-algorithm, graph-algorithms ## Books ### 1. Network Flow Algorithms **Author:** David P. Williamson Cambridge University Press text, posted free by the author with publisher permission. Covers maximum flows, minimum-cost flows, generalized and multicommodity flows, global minimum cuts, and electrical flows, with applications to computer vision and sports elimination. Based on Cornell and Stanford courses. **Difficulty:** Advanced | **Language:** English | **Price:** Free **Link:** https://www.networkflowalgs.com/ **Tags:** maximum-flow, minimum-cost-flow, multicommodity-flow, minimum-cuts, combinatorial-optimization ### 2. Network Flows: Theory, Algorithms, and Applications **Author:** Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin Standard graduate reference on network optimization. Gives self-contained treatments of shortest paths, maximum flows and minimum-cost flows, including polynomial-time algorithms and their analysis, plus more than 150 applications. Readers learn to model engineering and management problems as flows and solve them efficiently. **Difficulty:** Intermediate | **Language:** English | **Price:** Paid **Link:** https://www.amazon.com/dp/1292042702?tag=edmonddante07-20 **Tags:** books, mathematics-statistics, graph-theory --- *This content is part of Dantes.io - Your Treasure Map to Knowledge* *Curated by humans at Dantes.io. Personal study use welcome; republishing this curation requires permission (team@dantes.io).* View this page online: https://dantes.io/subject/network-flows