الگوریتم فورد-فولکرسون و ادموندز-کارپ

[قله بلند]

سلام

در مورد الگوریتم فورد-فولکرسون و ادموندز-کارپ سوال دارم

زمان اجرای الگوریتم فورد-فولکرسون رو نوشته

O(Ef)
که f در واقع جریان ماکزیمم هست. زمان پیدا کردن یک مسیر رو هم در این شبکه پسمانده، قرار داده

O(E)
ولی زمانی رو برای به هنگام کردن یال های مسیر در نظر نگرفته. چرا؟
و اینکه اگر از الگوریتم جستجوی اول-سطح برای یافتن مسیر در شبکه پسمانده استفاده شود به زمان

O(E)
می رسیم ولی فرض بر این نیست که الگوریتم فورد-فولکرسون از این روش استفاده می کند تا مسیر را بیاید.



و الگوریتم ادموندز-کارپ
اصولاً برای این، این الگوریتم به وجود آمد چون یافتن مسیر در شبکه پسمانده از روش BFS به دست می آید و زمان اجرا را

O(VE)
به دست می آورد که V در واقع تعداد رئوس است.
لطفاً نحوه تحلیل O(VE) رو شرح بدید که چگونه به این نتیجه می رسه. البته زمان نهایی در یک O(E) ضرب می شود.

با سپاس