概述
圖論中的一種理論與方法，研究網路上的一類最最佳化問題。1955年，T.E.哈里斯在研究鐵路最大通量時首先提出在一個給定的網路上尋求兩點間最大運輸量的問題。1956年，L.R.福特和D.R.富爾克森等人給出了解決這類問題的算法，從而建立了網路流理論。所謂網路或容量網路指的是一個連通的賦權有向圖D＝（V、E、C），其中V是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網路上的流就是由起點流向終點的可行流，這是定義在網路上的非負函式，它一方面受到容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。如果把下圖看作一個公路網，頂點v1…v6表示6座城鎮，每條邊上的權數表示兩城鎮間的公路長度。現在要問：若從起點v1將物資運送到終點v6去，應選擇那條路線才能使總運輸距離最短這樣一類問題稱為最短路問題。如果把上圖看作一個輸油管道網，v1表示傳送點，v6表示接收點，其他點表示中轉站，各邊的權數表示該段管道的最大輸送量。現在要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大這樣的問題稱為最大流問題。最大流理論是由福特和富爾克森於1956年創立的，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善。最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論套用的新途徑。
最大流問題僅注意網路流的流通能力，沒有考慮流通的費用。實際上費用因素是很重要的。例如在交通運輸問題中，往往要求在完成運輸任務的前提下，尋求一個使總運輸費用最省的運輸方案，這就是最小費用流問題。如果只考慮單位貨物的運輸費用，那么這個問題就變成最短路問題。由此可見，最短路問題是最小費用流問題的基礎。現已有一系列求最短路的成功方法。最小費用流(或最小費用最大流)問題，可以交替使用求解最大流和最短路兩種方法，通過疊代得到解決。
發展
目前網路流的理論和套用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網路流的分解與合成等新課題。網路流的套用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。求最大流有兩種常用的算法:
1、augment path，直譯為“增廣路”，其思想大致如下：原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜尋出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。
尋找通路的時候可以用DFS，BFS最短路等算法。就這兩者來說,BFS要比DFS快得多，但是編碼量也會相應上一個數量級。
增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個複雜得多的算法，就是預推進算法。
2、push label，直譯為“預推進”算法。
【等待完善】
