در بیشینهٔ جریان، می‌خواهیم بیشترین مقدار ممکن را از مبدأ به مقصد یک شبکه بفرستیم، بدون عبور از ظرفیت یال‌ها و بدون ایجاد یا ناپدیدکردن جریان در گره‌های میانی. پیدا‌کردن یک مسیرِ پُر، پایان مسئله نیست؛ شاید بتوان انتخاب قبلی را اصلاح کرد. یالِ معکوس در شبکهٔ باقیمانده، راهِ لغو بخشی از جریانِ قبلی را نشان می‌دهد. مثال این صفحه دقیقاً چنین لغوی را اجرا می‌کند.
پنج یالِ یک‌واحدی
گره‌ها S، A، B و T هستند. یال‌های اصلی S→A، S→B، A→B، A→T و B→T همگی ظرفیت۱ دارند. S مبدأ و T مقصد است. هیچ یالِ اصلیِ B→A نداریم. داده‌ها آموزشی‌اند؛ شبکهٔ واقعی تلفن، پهنای باند، نرخ تماس یا ظرفیت خدمات اپرا را شبیه‌سازی نکرده‌ایم.
روشِ این فایل، جست‌وجوی عمقی برای یافتن مسیرِ افزایشی در باقیمانده است؛ ترتیبِ همسایه‌ها ثابت انتخاب شده تا نقش لغو آشکار شود. این پیاده‌سازی Edmonds–Karp نیست؛ آن نام به انتخاب مسیرِ کوتاه‌تر با BFS مربوط است. مستند NetworkX را برای قرارداد باقیمانده خوانده‌ایم و خودِ کتابخانه را اجرا نکرده‌ایم.
مسیر اول فقط یک واحد می‌فرستد
DFS با ترتیبِ ثبت‌شده مسیر S→A→B→T را پیدا می‌کند. کمترین ظرفیتِ باقیماندهٔ مسیر۱ است؛ پس جریانِ S→A، A→B و B→T هر کدام۱ می‌شود. هنوز ظرفیتِ S→B و A→T آزاد است، ولی اگر فقط یال‌های اصلیِ دارای فضای خالی را ببینیم، از B به T جا نداریم و به اشتباه روی مقدار۱ متوقف می‌شویم.
| یال اصلی | پس از مسیر اول | پس از اصلاح دوم |
|---|---|---|
| S→A | ۱ | ۱ |
| S→B | ۰ | ۱ |
| A→B | ۱ | ۰ |
| A→T | ۰ | ۱ |
| B→T | ۱ | ۱ |
مسیر دوم از B به A برمی‌گردد
پس از ارسالِ یک واحد روی A→B، باقیمانده یک واحد امکانِ برگشتِ B→A دارد. این ظرفیتِ فیزیکیِ تازه نیست؛ اجازهٔ کم‌کردنِ همان انتخاب قبلی است. جست‌وجوی دوم مسیر S→B→A→T را در باقیمانده پیدا می‌کند. روی S→B یک واحد اضافه، روی A→B یک واحد کم و روی A→T یک واحد اضافه می‌کنیم. کل جریان از۱ به۲ می‌رسد.
در نتیجهٔ نهایی، A→B جریان۰ دارد و مسیرهای S→A→T و S→B→T هر کدام۱ حمل می‌کنند. برنامه برای هر تغییر برچسبِ «افزایشِ یال اصلی» یا «لغوِ جریانِ قبلی» ثبت می‌کند. تعبیرِ اشتباه این است که هم A→B با مقدار۱ را نگه داریم و هم B→A را یک جریان مستقلِ تازه بشماریم؛ در این نمونه، برگشت دقیقاً جریانِ A→B را صفر کرد.
قیدها را بعد از هر افزایش کنترل کنیم
بعد از هر مسیر، همهٔ جریان‌های یالِ اصلی بین صفر و ظرفیت‌اند. برای A و B جمعِ ورودی و خروجی برابر کنترل می‌شود؛ این گره‌ها تولیدکننده یا مصرف‌کننده نیستند. دفتر JSON علاوه بر مسیرها، وضعیت کامل پنج جریان را پس از هر تغییر نگه می‌دارد. مسیرِ باقیمانده را با یک مسیرِ حمل مستقل روی یال‌های اصلی یکی نگیرید؛ تغییرات باید روی جریانِ قبلی اعمال شوند.
یک اجرای نادرستِ جدا، امکان یال معکوس را عمداً حذف می‌کند و روی همین داده با جریان۱ متوقف می‌شود. بنابراین نقش یالِ برگشت در خروجی قابل مشاهده است. فایل، دو اجرای مستقل از جریانِ صفر دارد؛ ادامهٔ اجرای درست از وضعیتِ خراب نیست.
چرا جریان۲ واقعاً بیشینه است؟
یک برش، گره‌ها را به دو سمت تقسیم می‌کند که S یک طرف و T طرف دیگر باشد. ظرفیت یال‌های اصلیِ رو به بیرون از سمت S، سقفی برای هر جریان مجاز است. تابع مستقل هر چهار حالتِ قراردادن A و B را بررسی می‌کند؛ کمترین ظرفیتِ برش۲ است. از طرفی جریانِ مجاز۲ ساخته‌ایم؛ پس برای این مثال، سقف و مقدارِ قابل دستیابی برابرند.
در فایل، همهٔ ظرفیت‌ها ثابت و صحیح و یال‌های اصلی بدون جفتِ رفت‌وبرگشت‌اند. از کدِ کوچک، حل‌کنندهٔ عمومیِ همهٔ شبکه‌ها نسازید؛ برای یال‌های موازی، ظرفیت نامتناهی یا دو یال اصلیِ مخالف باید قرارداد نمایش را دقیق‌تر طراحی کرد. این متن زمانِ اجرای واقعی یا برتری ابزارها را اندازه نگرفته است.
کوتاه‌ترین مسیر وزن‌دار هزینهٔ یک مسیر را کمینه می‌کند و BFS و DFS قرارداد پیمایش دارند؛ هیچ‌کدام به‌تنهایی قید ظرفیت و اصلاحِ جریان را جایگزین نمی‌کنند. در راهکارهای اپرا ابتدا ورودی، اختیار و خروجی موردنیاز را مشخص کنید؛ این آموزش وجود موتور جریان در محصول را اعلام نمی‌کند.
فایل تمرین و منبع
کد کامل Python؛ محاسبه و کنترل‌های مستقل · ورودیِ ساخته‌شده، مراحل و خروجیِ اجرای واقعی
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.