1. Introduction to Network Flow

Getting Started with Competitive Programming

(an NPTEL course)

Module 1. Introduction to Network Flow

Here we setup the language of a flow network, identify what we are looking for, examine a natural greedy approach that doesn't work, and fix it so we get to the Ford-Fulkerson algorithm. By making some specific choices in this algorithm we obtain the Edmonds-Karp algorithm.

The module is split into three segments:

  • Introduction to the maxflow problem
  • Algorithms for maxflow
  • Implementing Edmonds-Karp

The code shown in these lectures can be found here. You can try it yourself via the UVa 820 problem, Internet Bandwidth.

Although not discussed, you can find the code for Dinic's algorithm here.

Other sources to learn about maxflow:

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>