Data Structures and Algorithms B
  • Introduction
  • Stable Marrage
  • Huffman Codes
    • ABL
    • Implementation
  • Graph Algorithms
    • Connect Component
    • Bipartiteness
    • Strongly Connected Components
      • Implementation
    • Topological Sort
      • Implementation 1
      • Implementation 2
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
      • Prims
        • Implementation 1
      • Kruskels
        • Implementation 1
      • Traveling Salesman Problem
    • k-Clustering
    • Dynamic Programming with Trees
      • Implementation 1
      • Implementation 2
    • Disjoint Sets
      • Implementation
    • Eularian Cycle
      • Implementation
    • Hamiltonian Path
      • Implementation
  • Divide and Conquer
    • Merge Sort
    • Integer Multiplication
    • Closest Pair
    • Master Method
  • Dynamic Programming
    • Interval Scheduling
    • Knapsack Problem
  • Network Flow
    • Maximum Network Flow
    • Improvements
    • Image Segmentation
  • String Algorithms
    • Z Algorithm
    • Boyer-Moore
    • Knuth-Morris-Pratt
    • Suffix Trees
      • Naive Implementation
      • Ukkonens Algorithm
        • Implementation
      • Applications
        • Longest Common Substring
        • Longest Palindromic Substring
        • Longest Repeated Substring
  • Randomized Algorithms
    • Bloom Filters
      • Implementation
Powered by GitBook
On this page
  • Intuition:
  • Algorithm
  • English
  • On Paper

Was this helpful?

  1. Network Flow

Maximum Network Flow

Intuition:

  • The goal is to discover the maximum amount of something we can push through a network system in which each path some limiting bottleneck. For example, Road systems, and water pipelines.

  • Big O: O(E*maximum flow)

Algorithm

English

  1. Initialize all flows to 0.

  2. Note a possible path in the residual network between the furthest two nodes (the source, and the sink). That is, find the path that will give you the greatest flow.

  3. Note the minimum in the path.

  4. Push the minimum flow through the augmented path to the sink.

    • Update the paths:

      • Subtract from the edge by the minimum

      • Add a reverse flow of value minimum

      • Note that reverse flow + subtracted edge will always = original flow.

  5. Once no other paths are possible to push in flow, the algorithm is complete.

  6. The maximum flow will be the sum of each augmented path you pushed into the sink from the source.

On Paper

  1. Choose and prioritize the augmented paths that provide the most network flow.

  2. Initial G_flow and G_residual

  3. Next augmentations:

    • G_r:

    • See b

  4. G_f:

    • Follow through the augmented path you’ve set up. Then, based on G_r, note whether your augmented path will flow through the directed arrows of G_r.

    • If it does, add to the current edge

    • If it does not follow the G_r augmented path, subtract.

PreviousNetwork FlowNextImprovements

Last updated 5 years ago

Was this helpful?