簡化您的工作流程：搜尋 miniwebtool。
添加插件
相關工具
鄰接矩陣計算機複數計算機戴克斯特拉最短路徑計算機漢密爾頓路徑檢查器旅行推銷員問題求解器 (TSP)
主頁 > 數學 > 進階數學計算 > 網路最大流計算機
 

網路最大流計算機

使用 Ford-Fulkerson 方法 (Edmonds-Karp) 計算有容量限制的有向網路中從源點到匯點的最大流。動畫演示每條增廣路徑，顯示殘留容量、飽和邊，以及證明最佳解的最小割劃分。

網路最大流計算機
快速範例：
教科書案例 (6 節點) 小型網路 經典 CLRS 類二分圖 矩陣輸入
邊格式：A -> B : 10（箭頭加容量），或 A, B, 10。
矩陣格式：每行一個橫列，C[i][j] 為邊 i → j 的容量（無邊則填 0）。對角線必須為 0。
以逗號或空格分隔標籤，每個對應一個矩陣行。預設為 S, A, B, …, T。

Embed 網路最大流計算機 Widget

網路最大流計算機

這款網路最大流計算機可以計算任何帶容量的有向網路中，從選定的源點 s 到選定的匯點 t 的最大流。它底層運行帶有廣度優先增廣路徑的 Ford-Fulkerson 方法（即 Edmonds-Karp 演算法），並記錄找到的每一條路徑，讓您可以逐次迭代地重播整個決策過程。結果頁面還會顯示最小割 — 證明您的流量值確實是最優的瓶頸分區。

什麼是最大流問題？

流量網路是一個有向圖 G = (V, E)，連同一個容量函數 c: E → ℝ≥0。其中區分了兩個頂點：源點 s（流量發源地）和匯點 t（流量消耗地）。流量 f 是分配在邊上的值 f(u, v) ≥ 0，且遵循：

容量限制： 0 ≤ f(u, v) ≤ c(u, v) 對於每一條邊 (u, v) 流量守恆： Σ f(w, v) = Σ f(v, w) 對於所有 v ∈ V \ {s, t} 流量值： |f| = Σ f(s, w) − Σ f(w, s) (離開 s 的淨流量)

最大流問題旨在尋找能使 |f| 最大化的流量 f。直觀來說：如果邊是具有給定容量的水管，您每秒可以從 s 運送多少公升的水到 t？

演算法原理 — 配合 BFS 的 Ford-Fulkerson

演算法在處理當前流量的同時維護一個剩餘圖。對於每條具有容量 c 和當前流量 f 的邊 (u, v)，剩餘圖包含：

在每次迭代中，它會在剩餘圖上執行從 s 到 t 的廣度優先搜尋 (BFS)。如果找到路徑，則路徑上的最小邊容量（即瓶頸）會加到路徑上每條前向邊的流量中，並從每條反向邊的流量中減去。這被稱為增廣路徑。當 BFS 再次執行卻無法到達 t 時，當前流量即為最優解。

當 剩餘圖中存在從 s 到 t 的增廣路徑 P 時： b ← 路徑 P 中邊 (u, v) 的最小剩餘容量 c_residual(u, v) 沿路徑 P 推送 b 單位的流量 // 更新剩餘圖與流量 返回 總流量 |f|

使用 BFS（而非任意路徑搜尋策略）將 Ford-Fulkerson 轉變為 Edmonds-Karp 演算法，其保證運行時間為 O(V · E²)。它還保證在邊容量為無理數時也能終止，而普通的 Ford-Fulkerson 則無法保證。

最大流最小割定理

割 (Cut) 是將頂點劃分為兩個集合 (S, T) 的分區，其中 s ∈ S 且 t ∈ T。其容量是從 S 到 T 的邊容量之和：

cap(S, T) = Σ c(u, v) 對於 u ∈ S, v ∈ T

最大流最小割定理 (Ford & Fulkerson, 1956) 指出：

最大流值 = 最小割容量

此工具會自動尋找最小割。在 Edmonds-Karp 終止後，它會在剩餘圖上從 s 執行最後一次 BFS；所到達的頂點形成 S，其餘頂點形成 T，且原始圖中所有橫跨 S → T 的邊都是飽和的。它們的容量之和恰好等於最大流值 — 在核心結果中顯示為「最小割容量 ✓ 確認最優性」。

專為學習設計的功能

輸入格式

1. 帶容量的邊列表

每行輸入一條邊。箭頭形式最易讀，但以下幾種替代方案也適用：

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

同樣接受：A, B, 10 · A B 10 · A -> B , 10。相同頂點對之間的多條邊將會被加總。

2. 容量矩陣

每行輸入一個橫列，數值以空格或逗號分隔。項目 C[i][j] 是從頂點 i 到頂點 j 的邊容量。使用 0 代表「無邊」。矩陣必須是正方形，且對角線必須為 0（不允許自環）。

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

在矩陣標籤欄位中輸入對應的頂點標籤（以逗號或空格分隔）。如果省略，標籤預設為 S, A, B, …, T。

最大流的應用

領域最大流的使用方式
運輸與物流鐵路/道路/管道網路每天從起點到終點能運輸多少貨物？
二分圖匹配將工作分配給工人，或將學生分配給專案。單位容量的最大流可得出最大匹配。
圖像分割計算機視覺中的 Boykov–Kolmogorov 最小割可將前景與背景像素分離。
網路可靠性最小割可識別出哪些最弱連結失效後會導致網路中斷。
專案時程管理閉包問題和選擇問題可以簡化為最小割問題。
棒球淘汰分析判斷一支球隊在數學上是否已與聯賽冠軍無緣。

範例解析

「教科書」快速範例編碼了一個具有源點 S 和匯點 T 的 6 節點網路。執行 Edmonds-Karp 會產生四條增廣路徑：

  1. S → A → B → T，瓶頸為 4（邊 A-B 是限制因素）。累計流量：4。
  2. S → A → D → T，瓶頸為 6。累計流量：10。
  3. S → C → D → T，瓶頸為 4（邊 D-T 現在是限制因素，僅剩 4）。累計流量：14。
  4. S → C → D → B → T，瓶頸為 5。累計流量：19。

演算法停止 — 不再存在增廣路徑。最小割為 (S = {S, C}, T = {A, B, D, T})，橫跨邊為 S → A (容量 10) 和 C → D (容量 9)，總和為 19 — 恰好等於最大流值。

如何使用此計算機

  1. 使用選項卡選擇輸入格式 — 邊列表（建議）或容量矩陣。
  2. 輸入您的網路。 您可以從快速範例開始並進行修改。若使用矩陣輸入，如果您想要 S, A, B, …, T 以外的名稱，請提供標籤。
  3. 指定源點和匯點（或留空以自動偵測 S 和 T）。
  4. 點擊計算最大流。 結果頁面會顯示最大流值、最小割分區、分層圖表視覺化、每一條增廣路徑、邊利用率表以及三個矩陣（容量、流量、剩餘流量）。
  5. 播放圖表下方的動畫以重播演算法的決策過程。點擊任何增廣路徑步驟可直接跳轉至該步驟。

限制

常見問題

什麼是最大流問題？

給定一個有向網路，其中每條邊都有非負容量，最大流問題在探討：在滿足每條邊的流量不超過其容量，且流入每個非源點、非匯點頂點的流量必須等於流出該頂點的流量這兩個規則下，從指定的源點 s 可以向匯點 t 推送多少流量？答案稱為最大流值。

什麼是 Ford-Fulkerson 方法？

Ford-Fulkerson 是計算最大流的一種通用技術。它反覆在剩餘圖中尋找從源點到匯點的增廣路徑，沿該路徑推送盡可能多的流量（瓶頸容量），然後更新剩餘圖。當不存在增廣路徑時，程序終止。當使用廣度優先搜尋 (BFS) 進行路徑選擇時，它被稱為 Edmonds-Karp 演算法，運行時間為 O(V · E²) 級別。

流量網路的最小割是什麼？

割是將頂點劃分為兩個集合 S 和 T 的分區，使得源點在 S 中，匯點在 T 中。割的容量是從 S 到 T 的邊容量之和。最小割是容量最小的割。著名的最大流最小割定理證明，最大流值始終等於最小割容量，因此找到其中一個就等於免費得到了另一個。

什麼是剩餘圖？

剩餘圖追蹤每條邊還能推送多少流量。對於每條原始邊 (u, v)，若容量為 c 且當前流量為 f，則剩餘圖包含一條容量為 c 減 f 的前向邊 (u, v)（剩餘容量）和一條容量為 f 的反向邊 (v, u)（可取消流量）。增廣路徑使用剩餘圖的邊，允許演算法撤銷之前的決定。

為什麼工具使用 BFS 尋找增廣路徑？

選擇使用廣度優先搜尋 (Edmonds-Karp) 尋找增廣路徑可以保證無論邊容量如何，都能在多項式時間內終止。普通的 Ford-Fulkerson 若使用任意路徑尋找策略，在病態輸入下可能會循環指數級次迭代，在無理數容量下甚至可能不終止。BFS 還會產生最短的增廣路徑，更易於閱讀和推理。

飽和邊代表什麼意思？

當邊的流量等於其容量時，該邊即為飽和，這意味著無法再在其上推送更多流量。飽和邊是網路的瓶頸，且每個最小割完全由從割的 S 側到 T 側的飽和邊組成。工具會以紅色突出顯示飽和邊，讓您一眼就能看到瓶頸結構。

延伸閱讀

引用此內容、頁面或工具為：

"網路最大流計算機" 於 https://MiniWebtool.com/zh-tw/網路最大流計算機/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊製作。更新日期：2026年4月22日

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

進階數學計算:

常用工具:

分數計算機隨機撲克牌產生器真心話大冒險產生器百分比增加計算機百分比增長率計算機斜邊計算機🎮 遊戲靈敏度轉換器隨機信用卡生成器羅馬數字轉換器相對標準偏差計算機磅轉公斤轉換器質數分解計算機比例計算機圓計算機kpa到psi轉換器最簡分數計算機毛利率計算機HEX計算機商和餘數計算機百分比折扣計算機kg到lbs轉換器百分比減少計算機圖片分割器校正鈣計算機MAC地址查找太陽、月亮與上升星座計算機 🌞🌙✨隨機字母生成器Instagram用戶ID查詢隨機名稱生成器年齡計算機百分比變化計算機百分比誤差計算機最小公倍數計算機反向文字查找並替換文字🌡️ 體感溫度計算機ANC計算機影片轉圖片擷取器年份天數計算機 - 今天是今年的第幾天簡單利息計算機坡度與傾斜度計算機複利計算機AI內容檢測器兩點間距離計算機Bar to PSI 轉換器隨機選擇器調整影片速度加價計算機定期存款計算機二次公式計算機迷宮產生器隨機餐點產生器SRT時間偏移標準偏差計算機 - 高精度多分數計算機📅 日期計算機樂透號碼生成器小字體生成器 ⁽ᶜᵒᵖʸ ⁿ ᵖᵃˢᵗᵉ⁾因子計算機分數百分比轉換器畢達哥拉斯定理計算機對數計算機分數到小數計算機音訊分割器模計算機CAGR計算機凱薩密碼工具合併影片PCB走線寬度計算機隨機數學題產生器影片壓縮器剪刀石頭布產生器cpm計算機平均值計算機隨機動物生成器橢圓 周長計算機賓果卡生成器比率與百分比計算機填字遊戲製作器克到磅轉換器文字重複工具最大公因子計算機百分比計算機FPS 轉換器星期幾計算機Zalgo文本生成器psi到kpa轉換器速度計算機文件大小轉換器速度轉換器YouTube頻道統計磅到克轉換器跑步配速計算機組合計算機⏱️ 小時計算機隨機英文單字產生器數獨產生器與求解器公因子計算機ERA計算機考拉茲猜想計算機隨機錦標賽對陣生成器我的幸運數字是什麼積分計算機OPS計算機圖片打碼工具Facebook用戶ID查詢HEX轉換器隨機顏色生成器可整除測試計算機百分比到ppm轉換器純利潤計算機保齡球計分計算機質數檢查器壓力轉換器隨機日期生成器斜率計算機總和計算機文本格式化工具SRT轉換為TXT工具科學記數法計算機AI標點符號添加器為影片新增浮水印隨機時間生成器隨機生日生成器十進製到科學記數法轉換器出生星期計算機小數到分數計算機線規計算機體積轉換器姓名靈數計算機條碼產生器排序數字🖱️ 點擊計數器GUID / UUID 生成器MAC地址產生器YouTube收益估算器行數統計工具不可見字元移除器投球命中率計算機血壓解讀器克到盎司轉換器刑期減免計算機棒球長打率計算機步數距離計算機演講時間計算機刪除線文字產生器樓梯計算機汽車貸款計算機線性迴歸計算機馬丁格爾策略計算機MP3循環播放器棒球打擊率計算機工時計算機淨利潤率計算機歐姆定律計算機燃油費用計算機階乘計算機鋼筋計算機PSI 轉 Bar 轉換器汽車折舊計算機工作搜尋器🌐 時區轉換器移除標點符號線上工具圖片壓縮器直角三角形計算機樣本量計算機黃金比例計算機隨機化數字影片分割器游泳配速計算機發音音標轉換器GIF 轉 MP4 轉換器圓柱體體積計算機 高精度隨機貓狗名字產生器上壘率計算機弧長計算機名人名言搜尋 (英文)心算訓練器角度轉換器預產期計算機橢圓面積計算機複數計算機多項式因式分解計算機比較分數計算機隨機字符串生成器WHtR計算機凱利公式計算機愛情兼容性計算機正方形計算機GIF 製作器Log Base 10 計算機倒立文本產生器土星回歸計算機數字轉分數轉換器比率計算機百分比到小數轉換器預期壽命計算機功率轉換器常規時間到小數時間轉換器血糖轉換器CGPA轉百分比轉換器簡易評分器 EZ Grader養育孩子成本計算機寶寶奶量計算機尿布尺寸計算機嬰兒名字產生器寶寶眼睛顏色預測器兒童BMI百分位計算機兒童身高預測器hcg翻倍時間計算機試管嬰兒預產期計算機著床計算機中國生男生女預測器ISO 8601 日期格式化工具儒略日轉換器午睡計算機月相計算機日出日落計算機世界時鐘日期至羅馬數字轉換器退休倒數計時戒癮天數計算機半歲生日計算機紀念日計算機週數計算機小費分配計算機電子郵件行銷ROI計算機每筆潛在客戶成本計算機營運資本計算機邊際貢獻計算機FIFO / LIFO 計算機安全庫存計算機再訂購點計算機經濟訂購量eoq計算機折舊計算機手工藝品定價計算機批發價格計算機Shopify 利潤計算機Amazon FBA 計算機eBay費用計算機Etsy費用計算機Stripe 手續費計算機PayPal手續費計算機投注賠率轉換器十一奉獻計算機天課計算機英國印花稅計算機HRA免稅計算機服務酬金計算機NPS計算機EPF計算機PPF計算機RD計算機SWP計算機稅前薪資倒推計算機貸款比較計算機信用使用率計算機CD階梯計算機美國國庫券T-Bill計算機I 系列儲蓄債券計算機529大學儲蓄計算機HSA計算機遣散費計算機加薪計算機發票產生器出差津貼計算機里程報銷計算機房租漲幅計算機按比例租金計算機房租負擔能力計算機汽車落地價計算機購車預算計算器機車貸款計算機房車貸款計算機船舶貸款計算機土地貸款計算機建築貸款計算機只付利息抵押貸款計算機氣球貸款計算機房貸點數計算機PMI計算機雙週房貸還款計算機ARM浮動利率房貸計算機VA貸款計算機實領薪資計算機AI SQL 查詢產生器AI正規表達式產生器AI 資料視覺化工具（貼上 CSV）AI文字語氣分析器AI履歷分析器AI單位轉換器自然語言AI道歉信產生器AI禮貌藉口產生器AI 旅行行程產生器AI閱讀清單產生器AI健身計劃產生器AI膳食計畫生成器AI禮物點子產生器AI食譜產生器依現有食材獎學金投資報酬率計算機大學費用計算機語言學習流利度小時數計算機詞彙測驗產生器康乃爾筆記產生器學習曲線計算機閃卡間隔重複排程器顏料調色計算機磁磚填縫劑計算機洗碗機裝載最佳化工具洗滌劑用量計算機染髮劑調配計算機列印成本計算機燃氣與電力成本比較禮品卡小費計算機搬家紙箱數量計算機儲物單元尺寸計算機膠囊衣櫥搭配計算機皮帶長度計算機液壓缸推力計算機滑輪組計算機齒輪比計算機機械比熱容計算機熱膨脹計算器熱傳遞計算機伯努利方程式計算機雷諾數計算機太陽位置計算機潮汐時間計算器星空可見度計算機繩結打法參考工具睡袋溫度評級指南帳篷地布尺寸計算機背包旅行食物重量計算機奈史密斯健行配速計算機刺繡線長度計算機樹脂灌模容量計算機串珠圖案計算機陶土收縮率計算機折紙紙張大小計算機被子滾邊計算機十字繡繡線計算機針織圖案計算機編織針尺寸轉換器鉤針尺寸轉換器馬匹乾草計算機寵物航空旅行航空箱尺寸查詢器爬蟲棲息地UVB計算機鳥籠尺寸計算機魚缸加熱棒瓦數計算機貓砂盆數量計算機前照燈光束距離計算機引擎壓縮比計算機輪胎胎紋磨損計算機拖車舌重計算機車輛重量分佈計算機旅行費用分攤計算機剎車距離計算機工傷賠償計算機遺產分配計算機商標分類查詢計算機專利申請費計算機銷售稅關聯檢查器訴訟時效計算機Airbnb 定價優化工具室友房租分攤計算機Section 8 租金計算機BRRRR 方法計算機現金對現金報酬率計算機租金收益率計算機1031 交換計算機財富成長視覺化工具午餐花費計算機健身房 vs 居家健身花費計算機咖啡花費計算機遠端工作省錢計算機副業ROI計算機訂閱費用追蹤器SaaS定價計算機自由接案專案報價計算機煙燻木材搭配指南發酵時間計算機醃製時間計算機飲食限制食譜篩選器香料替代查找器咖啡因半衰期追蹤器標準杯計算機葡萄酒搭配建議器攀岩難度等級轉換器自行車齒輪比計算機釣魚結強度計算機瑜伽體式保持計時器游泳SWOLF計算機跑步成績預測計算機拳擊出拳力量計算機橄欖球得分計算機板球得分率計算機足球 xG預期進球計算機網球計分器Wells評分計算機 (DVT/PE)格拉斯哥昏迷指數計算機阿普加評分計算機FFMI計算機庫珀12分鐘跑步計算機一英里步行測試Rockport計算機瘦體重力量計算器碳水化合物胰島素比例計算機胰島素敏感係數計算機希伯來曆轉換器伊斯蘭曆轉換器農曆轉換器跨文化年齡計算機多久以前計算機還有多久倒數計算機日期模式產生器中間日期計算機日期加上工作日工作日計算機詞頻分析器句子長度變異分析器海明威風格可讀性編輯器維吉尼亞密碼工具埃特巴什密碼工具ROT13編碼解碼器EXIF 資料檢視與移除工具豬拉丁文翻譯器倒推首字母縮寫產生器首字母縮寫產生器全字母句檢查器漏字文檢測器圖片轉SVG描摹器圖片轉 ASCII 藝術轉換器JSON Schema 產生器TypeScript 線上演練場Less 到 CSS 編譯器SCSS轉CSS編譯器SVG 轉 React/JSX 轉換器查詢字串產生器URL解析器UUID驗證和解碼器HTTP狀態碼參考cURL指令建構器謝爾賓斯基三角形產生器3D曲面繪圖器極座標方程繪圖器茱莉亞集合生成器曼德博集合探索器L-System分形產生器Delaunay 三角剖分生成器Voronoi 圖生成器萬花尺圖案產生器鑲嵌圖案產生器六標準差製程能力計算機YouTube縮圖下載器隨機RPG角色生成器