خوارزمية التدفق الأقصى بتقنية الدفع وإعادة التسمية

في مجال التحسين الرياضي ، تُعدّ خوارزمية الدفع وإعادة التسمية (أو خوارزمية التدفق المسبق والدفع ) خوارزميةً لحساب أقصى تدفقات في شبكة تدفق . ويُشتق اسم "الدفع وإعادة التسمية" من العمليتين الأساسيتين المستخدمتين في الخوارزمية. فخلال تنفيذها، تحافظ الخوارزمية على "تدفق مسبق" وتحوله تدريجيًا إلى أقصى تدفق عن طريق نقل التدفق محليًا بين العقد المتجاورة باستخدام عمليات الدفع، وذلك بتوجيه من شبكة مقبولة يتم الحفاظ عليها بواسطة عمليات إعادة التسمية . في المقابل، تُجري خوارزمية فورد-فولكرسون عمليات توسيع شاملة تُرسل التدفقات عبر مسارات من المصدر وصولًا إلى المصب. ^{[ 1 ]}

تُعتبر خوارزمية الدفع وإعادة التسمية من أكثر خوارزميات التدفق الأقصى كفاءة. تتميز الخوارزمية العامة بتعقيد زمني متعدد الحدود $O (V²E) ،$ وهو أكثر كفاءة تقاربياً من خوارزمية إدموندز-كارب $O (VE²)$ . ^[²^] تحقق بعض المتغيرات الخاصة بالخوارزمية تعقيدات زمنية أقل. يتميز المتغير القائم على قاعدة اختيار عقدة التسمية الأعلى بتعقيد $زمني$ $O$ $($ $V²\sqrtE$ $)$ $،$ ويُعتبر عموماً المعيار لخوارزميات التدفق الأقصى. $[$ ³^]^[⁴^]^يمكن تحقيق تعقيد زمني شبه مكعب $O$ $($ $VE$ $log($ $V²/$ $E$ $)$ $)$ ^{باستخدام الأشجار الديناميكية، [2]} $على$ الرغم من ^أنها $أقل$ ^كفاءة $عملياً$ .

تم توسيع خوارزمية الدفع وإعادة التسمية لحساب تدفقات التكلفة الدنيا . ^{[ 5 ]} وقد أدت فكرة تسميات المسافة إلى خوارزمية مسار مُعززة أكثر كفاءة، والتي بدورها يمكن دمجها مرة أخرى في خوارزمية الدفع وإعادة التسمية لإنشاء نسخة ذات أداء تجريبي أعلى. ^{[ 4 ]}^{[ 6 ]}

تاريخ

التدفق المسبق هو تدفق قد يكون فيه إجمالي كمية التدفق الداخلة إلى رأس ما أكبر من إجمالي كمية التدفق الخارجة منه، مما يسمح للخوارزمية بتغيير التدفق على قوس واحد. ^{[ 7 ]} طُورت هذه الفكرة في الأصل على يد ألكسندر ف. كارزانوف ونُشرت عام 1974 في مجلة "سوفيت ماثيماتيكاتيكال دوكلادي" العدد 15. استخدمت خوارزمية التدفق المسبق هذه أيضًا عملية دفع؛ إلا أنها استخدمت المسافات في الشبكة المساعدة لتحديد مكان دفع التدفق بدلًا من نظام تصنيف. ^{[ 2 ]}^{[ 8 ]}

صُممت خوارزمية الدفع وإعادة التسمية بواسطة أندرو ف. غولدبيرغ وروبرت تارجان . عُرضت الخوارزمية لأول مرة في نوفمبر 1986 في مؤتمر STOC '86: وقائع الندوة السنوية الثامنة عشرة لجمعية ACM حول نظرية الحوسبة، ثم نُشرت رسميًا في أكتوبر 1988 كمقال في مجلة $ACM$ . تُفصّل كلتا الورقتين شكلًا عامًا للخوارزمية ينتهي بـ $O (V²E)،$ بالإضافة إلى تطبيق تسلسلي بـ $O ($ $V³$ $)$ $، وتطبيق بـ$ $O (VE log( V²/ E)) باستخدام$ الأشجار الديناميكية، وتطبيق متوازٍ/موزع. ^{[ 2 ]}^{[ 7 ]} كما هو موضح في ^{[ 9 ]} $،$ أدخل غولدبيرغ وتارجان تسميات المسافة من خلال دمجها في خوارزمية التدفق الأقصى المتوازية ليوسي شيلواخ وأوزي فيشكين . ^{[ 10 ]}

المفاهيم

التعريفات والرموز

يترك:

لتكن $G$ $= ($ $V$ $,$ $E$ $)$ شبكة ذات دالة سعة $c : V \times V \to ℝ\infty$ ،
$F = (G, c, s, t)$ شبكة تدفق ، حيث $s \in V$ و $t \in V$ (مع s ≠ t) هما رأسي المصدر والمصبالمختارين على التوالي،
$f : V \times V \to ℝ$ تشير إلى تدفق مسبق في $F$ ،
$x f : V \to ℝ$ ترمز إلى دالة الزيادة بالنسبة للتدفق $f$ ، المعرفة بواسطة $x f (u) = Σ v \in V f (v, u) - Σ v \in V f (u, v)$ ،
$c f : V \times V \to ℝ \infty$ تمثل دالة السعة المتبقية بالنسبة للتدفق $f$ ، المعرفة بواسطة $c f (e) = c (e) - f (e)$ ،
$E f \subset E$ هي الحواف حيث $f < c$ ،

و

$G f (V, E f)$ تشير إلى الشبكة المتبقية لـ $G$ بالنسبة للتدفق $f$ .

تستخدم خوارزمية الدفع وإعادة التسمية دالة تسمية صحيحة غير سالبة ، تعتمد على تسميات المسافة ، أو الارتفاعات ، على العقد لتحديد الأقواس التي يجب اختيارها لعملية الدفع. يُرمز لهذه الدالة بالرمز $𝓁 : V \to ℕ$ . يجب أن تستوفي هذه الدالة الشروط التالية لكي تُعتبر صحيحة:

التسمية الصحيحة :

𝓁(u) \leq 𝓁(v) + 1

لجميع

(u, v) \in E f

حالة المصدر :

𝓁(s) = | V |

ترشيد استهلاك المياه في الأحواض :

𝓁(t) = 0

في الخوارزمية، تُثبَّت قيمتا $s$ و $t . يُمثِّل$ $𝓁(u)$ حدًّا أدنى للمسافة غير الموزونة من $u$ إلى $t$ في $G f$ إذا كان الوصول إلى $t$ ممكنًا من $u$ . أما إذا انقطعت الصلة بين $u و$ $t$ ، فإن $𝓁(u) - | V |$ يُمثِّل حدًّا أدنى للمسافة غير الموزونة من $u$ إلى $s$ . ونتيجةً لذلك، إذا وُجدت دالة تصنيف صالحة، فلن توجد مسارات $s - t$ في $G f،$ لأنه لا يمكن أن يتجاوز طول أيٍّ من هذه المسارات $| V | - 1$ .

يُطلق على القوس $(u, v) \in E f اسم$ $القوس$ المقبول إذا كان $𝓁($ $u$ $) = 𝓁($ $v$ $)$ $+ 1.$ تتكون الشبكة المقبولة $G̃f$ $($ $V$ $,$ $Ẽf$ $)$ من مجموعة الأقواس $e$ $\in$ $E$ $f$ المقبولة. الشبكة المقبولة غير دورية.

بالنسبة لتدفق ثابت $f$ ، يُطلق على الرأس $v \notin {s, t}$ اسم نشط إذا كان لديه فائض موجب بالنسبة إلى $f$ ، أي $x f (u) > 0$ .

العمليات

التهيئة

تبدأ الخوارزمية بإنشاء رسم بياني متبقٍ، وتهيئة قيم التدفق المسبق إلى الصفر، ثم تنفيذ مجموعة من عمليات الدفع المشبعة على الأقواس المتبقية $(s, v)$ الخارجة من المصدر، حيث $v ∈ V \ { s }$ . وبالمثل، تُهيأ التسميات بحيث تكون التسمية عند المصدر هي عدد العقد في الرسم البياني، $𝓁(s) = | V |$ ، وتُعطى جميع العقد الأخرى تسمية صفرية. بمجرد اكتمال التهيئة، تُنفذ الخوارزمية عمليات الدفع أو إعادة التسمية بشكل متكرر على العقد النشطة حتى يتعذر تنفيذ أي عملية قابلة للتطبيق.

يدفع

تُطبق عملية الدفع على قوس خارجي مقبول $(u, v)$ لعقدة نشطة $u$ في $G f$ . وهي تنقل $min{x f (u), c f (u, v)}$ وحدة من التدفق من $u$ إلى $v$ .

push(u, v): تحقق من أن x _f [u] > 0 و 𝓁[u] == 𝓁[v] + 1 Δ = min(x _f [u], c[u][v] - f[u][v]) f[u][v] += Δ f[v][u] -= Δ x _f [u] -= Δ x _f [v] += Δ

تُسمى عملية الدفع التي تؤدي إلى وصول $f (u, v) إلى$ $c (u, v)$ بالدفع المُشبع ، لأنها تستغل كامل السعة المتاحة للقوس المتبقي. أما في حالة الدفع غير المُشبع، فيتم دفع كل الطاقة الزائدة عند العقدة عبر القوس المتبقي .

إعادة تسمية

تُطبَّق عملية إعادة التسمية على عقدة نشطة $u$ ليست مصدرًا ولا مصبًا، ولا تحتوي على أي أقواس خارجية مقبولة في $G f$ . تُعدِّل هذه العملية $𝓁(u)$ لتكون القيمة الدنيا التي تُنشئ قوسًا خارجيًا مقبولًا. لاحظ أن هذا يزيد دائمًا من قيمة $𝓁(u)$ ولا يُنشئ أبدًا قوسًا حادًا، وهو القوس $(u, v)$ الذي يحقق الشرطين $c f (u, v) > 0$ و $𝓁(u) > 𝓁(v) + 1$ .

إعادة تسمية(u): تحقق من أن x _f [u] > 0 و 𝓁[u] <= 𝓁[v] لجميع v بحيث c _f [u][v] > 0 𝓁[u] = 1 + min(𝓁[v] لجميع قيم v بحيث يكون c _f [u][v] > 0)

تأثيرات الدفع وإعادة التسمية

بعد عملية الدفع أو إعادة التسمية، تظل $𝓁$ دالة تسمية صالحة بالنسبة إلى $f$ .

بالنسبة لعملية الدفع على قوس مقبول $(u, v)$ ، قد تضيف قوسًا $(v, u)$ إلى $E f$ ، حيث $𝓁(v) = 𝓁(u) - 1 \leq 𝓁(u) + 1$ ؛ وقد تزيل أيضًا القوس $(u, v)$ من $E f$ ، حيث تزيل فعليًا القيد $𝓁(u) \leq 𝓁(v) + 1$ .

لإثبات أن عملية إعادة تسمية العقدة $u$ تحافظ على صحة $𝓁(u)$ ، لاحظ أن هذا مضمون بشكل بديهي بحسب التعريف بالنسبة للأقواس الخارجية لـ u في $G f$ . أما بالنسبة للأقواس الداخلية لـ $u$ في $G f$ $، فإن 𝓁(u)$ المُحسّنة لا يمكنها إلا أن تُحقق القيود بشكل أقل صرامة، دون أن تنتهكها.

خوارزمية الدفع وإعادة التسمية العامة

تُستخدم خوارزمية الدفع وإعادة التسمية العامة كإثبات للمفهوم فقط، ولا تتضمن تفاصيل التنفيذ حول كيفية اختيار عقدة نشطة لعمليتي الدفع وإعادة التسمية. ستنتهي هذه النسخة العامة من الخوارزمية في $زمن$ $قدره$ $O (V²E)$ .

بما أن $𝓁(s) = | V |$ و $𝓁(t) = 0$ ، ولا توجد مسارات أطول من $| V | - 1$ في $G f$ ، فلكي يحقق $𝓁(s)$ شرط التسمية الصحيح ، يجب فصل $s عن$ $t$ . عند التهيئة، تُحقق الخوارزمية هذا الشرط بإنشاء تدفق أولي $f$ يُشبع جميع الأقواس الخارجة من $s$ ، وبعد ذلك يصبح $𝓁(v) = 0$ صحيحًا بشكل بديهي لجميع $v ∈ V \ { s , t }$ . بعد التهيئة، تُنفذ الخوارزمية بشكل متكرر عملية دفع أو إعادة تسمية مناسبة حتى لا تنطبق أي من هذه العمليات، وعندها يتحول التدفق الأولي إلى تدفق أقصى.

generic-push-relabel(G, c, s, t): أنشئ تدفقًا مسبقًا f يُشبع جميع الأقواس الخارجية لـ s ليكن 𝓁[s] = |V| وليكن 𝓁[v] = 0 لكل v ∈ V \ {s} طالما توجد عملية دفع أو إعادة تسمية قابلة للتطبيق، قم بتنفيذ العملية

الصواب

تحافظ الخوارزمية على شرط أن يكون $𝓁$ تصنيفًا صحيحًا أثناء تنفيذها. ويمكن إثبات ذلك بفحص تأثير عمليتي الدفع وإعادة التصنيف على دالة التصنيف $𝓁$ . تزيد عملية إعادة التصنيف قيمة التصنيف بمقدار الحد الأدنى المرتبط بها زائد واحد، وهو ما يحقق دائمًا الشرط $𝓁(u) \leq 𝓁(v) + 1.$ يمكن لعملية الدفع إرسال التدفق من $u$ إلى $v$ إذا كان $𝓁(u) = 𝓁(v) + 1. قد يؤدي ذلك$ $إلى$ إضافة $(v, u)$ إلى $Gf ،$ $وقد يؤدي أيضًا إلى$ حذف $(u, v)$ منها . لن تؤثر إضافة $($ $v$ $,$ $u$ $)$ إلى $Gf$ $على$ $صحة التصنيف لأن 𝓁($ $v$ $) = 𝓁($ $u$ $) - 1$ . يؤدي حذف $($ $u$ $,$ $v$ $)$ من $G$ $f$ إلى إزالة القيد المقابل لأن خاصية التسمية الصحيحة $𝓁($ $u$ $) \leq 𝓁($ $v$ $) + 1$ تنطبق فقط على الأقواس المتبقية في $G$ $f$ . ^[⁷^]

إذا وُجد تدفق مسبق $f$ وتسمية صالحة $𝓁$ له $،$ فلا يوجد مسار مُعزِّز من $s$ إلى $t$ في الرسم البياني المتبقي $G f$ . يمكن إثبات ذلك بالتناقض بناءً على المتباينات التي تظهر في دالة التسمية عند افتراض وجود مسار مُعزِّز. إذا انتهت الخوارزمية، فإن جميع العقد في $V \ { s , t }$ تكون غير نشطة. هذا يعني أن جميع $v ∈ V \ { s , t }$ ليس لديها تدفق زائد، وبدون فائض، فإن التدفق المسبق $f$ يُحقق شرط حفظ التدفق ويمكن اعتباره تدفقًا طبيعيًا. هذا التدفق هو التدفق الأقصى وفقًا لنظرية الحد الأقصى للتدفق والحد الأدنى للقطع، نظرًا لعدم وجود مسار مُعزِّز من $s$ إلى $t$ . ^{[ 7 ]}

لذلك، ستعيد الخوارزمية أقصى تدفق عند الانتهاء.

تعقيد الخطة

لتقدير التعقيد الزمني للخوارزمية، يجب تحليل عدد عمليات الدفع وإعادة التسمية التي تحدث داخل الحلقة الرئيسية. ويتم تحليل أعداد عمليات إعادة التسمية، وعمليات الدفع المشبعة، وعمليات الدفع غير المشبعة بشكل منفصل.

في الخوارزمية، يمكن إجراء عملية إعادة التسمية على الأكثر $(2| V | - 1)(| V | - 2) < 2| V | ²$ مرة. وذلك لأن قيمة التسمية $𝓁(u)$ لأي عقدة u لا يمكن أن تنخفض أبدًا، وقيمة التسمية القصوى هي $2| V | - 1$ على الأكثر لجميع العقد. هذا يعني أنه يمكن نظريًا إجراء عملية إعادة التسمية $2| V | - 1$ مرة لجميع العقد $V \ { s , t }$ (أي $| V | - 2$ $)$ . ينتج عن ذلك حد زمني قدره $O (V²)$ لعملية إعادة التسمية.

كل عملية دفع مشبعة على قوس مقبول $(u, v)$ تُزيل القوس من $G f$ . ولإعادة إدخال القوس إلى $G f$ لعملية دفع مشبعة أخرى، يجب أولاً إعادة تسمية $v$ ، ثم دفع القوس $(v, u)$ ، ثم إعادة تسمية $u . في هذه العملية، تزداد قيمة$ $𝓁(u)$ بمقدار اثنين على الأقل. لذلك، يوجد $O (V)$ عملية دفع مشبعة على $(u, v)$ ، والعدد الإجمالي لعمليات الدفع المشبعة لا يتجاوز $2| V || E |$ . ينتج عن ذلك حد زمني قدره $O (VE)$ لعمليات الدفع المشبعة.

يمكن تحديد عدد عمليات الدفع غير المشبعة باستخدام دالة الجهد . نستخدم دالة الجهد $Φ = Σ [u \in V \land x f (u) > 0] 𝓁(u)$ (أي أن $Φ$ هي مجموع تسميات جميع العقد النشطة). من الواضح أن $Φ$ تساوي $صفرًا$ في البداية وتبقى غير سالبة طوال تنفيذ الخوارزمية. يمكن لكل من إعادة التسمية وعمليات الدفع المشبعة زيادة قيمة $Φ$ . مع ذلك، يجب أن تساوي قيمة $Φ$ صفرًا عند انتهاء الخوارزمية، إذ لا يمكن أن تبقى أي عقد نشطة في نهاية تنفيذها. هذا يعني أنه خلال تنفيذ الخوارزمية، يجب أن تُعوض عمليات الدفع غير المشبعة الفرق بين عمليات إعادة التسمية وعمليات الدفع المشبعة حتى تنتهي قيمة $Φ عند الصفر. يمكن لعملية إعادة التسمية زيادة قيمة$ $Φ بمقدار$ $(2| V | - 1)(| V | - 2)$ على الأكثر . يؤدي الضغط المُشبع على $(u, v)$ إلى تنشيط $v$ إذا كان غير نشط قبل الضغط، مما يزيد $Φ$ بمقدار $2| V | - 1$ على الأكثر . وبالتالي، فإن المساهمة الكلية لجميع عمليات الضغط المُشبع في $Φ هي$ $(2| V | - 1)(2| V || E |)$ على الأكثر . أما الضغط غير المُشبع على $(u, v)$ فيؤدي دائمًا إلى تعطيل $u$ ، ولكنه قد يُنشط $v$ أيضًا كما في الضغط المُشبع. ونتيجة لذلك، فإنه يُقلل $Φ$ بمقدار $𝓁(u) - 𝓁(v) = 1$ على الأقل . بما أن عمليات إعادة التسمية وعمليات الدفع المشبعة تزيد من قيمة $Φ$ ، فإن العدد الإجمالي لعمليات الدفع غير المشبعة يجب أن يعوض الفرق بين $(2| V | - 1)(| V | - 2) + (2| V | - 1)(2| V || E |) \leq 4| V | ² | E |$ . ينتج عن ذلك حد زمني قدره $O (V²E)$ لعمليات الدفع غير $المشبعة$ $.$

باختصار، تُنفّذ الخوارزمية $O (V²)$ من عمليات إعادة التسمية، و $O$ $(VE) من$ عمليات الدفع المُشبعة، و $O$ $(V²E) من$ ^عمليات $الدفع غير المُشبعة$ . يمكن تصميم هياكل البيانات لاختيار وتنفيذ عملية مناسبة في زمن $O (1) . لذا،$ $فإن$ التعقيد الزمني للخوارزمية هو $O (V²E)$ . ^{[ 1 ]}^[ $7$ ^]

مثال

فيما يلي مثال على تنفيذ خوارزمية الدفع وإعادة التسمية العامة، كما هو موضح أعلاه، على مخطط تدفق الشبكة البسيط التالي.

الرسم البياني الأولي لشبكة التدفق

الرسم البياني النهائي لشبكة التدفق الأقصى

في المثال، تُشير القيمتان h و e إلى التسمية $𝓁$ والزيادة $x f$ ، على التوالي، للعقدة أثناء تنفيذ الخوارزمية. يحتوي كل رسم بياني متبقٍ في المثال على الأقواس المتبقية ذات السعة الأكبر من الصفر فقط. قد يحتوي كل رسم بياني متبقٍ على عدة تكرارات لحلقة تنفيذ العملية .

عملية (عمليات) الخوارزمية	الرسم البياني المتبقي
قم بتهيئة الرسم البياني المتبقي عن طريق ضبط التدفق المسبق على القيم 0 وتهيئة التسمية.
يتم تنفيذ عملية الدفع التشبعي الأولية عبر جميع أقواس التدفق المسبق الخارجة من المصدر، $s$ .
يتم إعادة تسمية العقدة $a$ من أجل دفع تدفقها الزائد نحو المصرف، $t$ . ثم يتم دفع الفائض عند $النقطة أ إلى$ $النقطة ب$ ثم $د$ في دفعتين متتاليتين مشبعتين؛ مما يترك النقطة $أ$ مع بعض الفائض.

مرة أخرى، يتم إعادة تسمية $a$ من أجل دفع فائضها على طول الباقي الموجب الأخير المتبقي (أي دفع الفائض مرة أخرى إلى $s$ ). ثم يتم إزالة العقدة $a$ من مجموعة العقد النشطة.

أعد تسمية $b$ ثم ادفع الزيادة إلى $t$ و $c$ .
أعد تسمية $c$ ثم ادفع الزيادة إلى $d$ .
أعد تسمية $d$ ثم ادفع فائضها إلى $t$ .
وهذا يجعل العقدة $b$ هي العقدة النشطة الوحيدة المتبقية، لكنها لا تستطيع دفع تدفقها الزائد نحو المصرف. أعد تسمية $b$ ثم ادفع فائضها نحو المصدر، $s$ ، عبر العقدة $a$ .

ادفع آخر جزء زائد في $الخلف$ إلى المصدر، $s$ . لا توجد عقد نشطة متبقية. تنتهي الخوارزمية وتعيد أقصى تدفق للرسم البياني (كما هو موضح أعلاه).

يمكن تشغيل المثال (ولكن مع تدفق أولي قدره 0) هنا بشكل تفاعلي.

التطبيقات العملية

على الرغم من أن خوارزمية الدفع وإعادة التسمية العامة تتطلب تعقيدًا زمنيًا $قدره$ $O (V²E) ،$ إلا أن التطبيقات الفعالة تحقق تعقيدًا زمنيًا $قدره$ $O (V³)$ أو أقل من خلال تطبيق قواعد مناسبة لاختيار عمليات الدفع وإعادة التسمية المناسبة. ويمكن تحسين الأداء التجريبي بشكل أكبر باستخدام أساليب استدلالية.

بنية بيانات "القوس الحالي" وعملية التفريغ

تُعدّ بنية بيانات "القوس الحالي" آليةً لزيارة الجيران الداخليين والخارجيين لعقدةٍ ما في شبكة التدفق بترتيبٍ دائري ثابت. إذا تم إنشاء قائمة مرتبطة أحادية للجيران لعقدةٍ ما، فيمكن أن تكون بنية البيانات بسيطةً كمؤشرٍ إلى القائمة يتنقل عبرها ويعود إلى بدايتها عند الوصول إلى نهايتها.

يمكن تعريف عملية التفريغ بناءً على بنية بيانات "current-arc". تُطبق عملية التفريغ على عقدة نشطة، وتدفع التدفق منها بشكل متكرر حتى تصبح غير نشطة، مع إعادة تسميتها حسب الحاجة لإنشاء أقواس مقبولة في العملية.

التفريغ(u): طالما أن x _f [u] > 0 ، إذا كان التيار-القوس[u] قد وصل إلى نهاية الجيران[u] ، إعادة تسمية (u) إعادة ضبط القوس الحالي[u] وإلا فليكن (u, v) = current-arc[u] إذا كان (u, v) مقبولاً . push(u, v) لنفترض أن current-arc[u] يشير إلى الجار التالي لـ u

إن إيجاد الحافة المقبولة التالية للمضي قدماً له $O(1)$ التعقيد المُستهلك . لا ينتقل مؤشر القوس الحالي إلى الجار التالي إلا عندما تكون الحافة المؤدية إلى الجار الحالي مشبعة أو غير مقبولة، ولا يمكن لأي من هاتين الخاصيتين أن تتغير حتى العقدة النشطة. $u$ يُعاد تسميتها. لذلك، عندما ينحرف المؤشر، لا توجد حواف غير مشبعة مقبولة، وعلينا إعادة تسمية العقدة النشطة. $u$ لذلك بعد تحريك المؤشر $O(V)$ يتم دفع ثمن الأوقات من قبل $O(V)$ عملية إعادة التسمية. ^{[ 7 ]}

قواعد اختيار العقدة النشطة

يُختزل تعريف عملية التفريغ خوارزمية الدفع وإعادة التسمية إلى اختيار عقدة نشطة للتفريغ بشكل متكرر. وتختلف الخوارزمية في تعقيدها الزمني تبعًا لقاعدة الاختيار. وللاختصار، سنتجاهل $s$ و $t$ عند الإشارة إلى العقد في المناقشة التالية.

قاعدة اختيار FIFO

تقوم خوارزمية الدفع وإعادة التسمية FIFO ^{[ 2 ]} بتنظيم العقد النشطة في طابور. يمكن إدخال العقد النشطة الأولية بترتيب عشوائي. تزيل الخوارزمية دائمًا العقدة الموجودة في مقدمة الطابور لتفريغها. عندما تصبح عقدة غير نشطة نشطة، تُضاف إلى مؤخرة الطابور.

تتمتع الخوارزمية بتعقيد زمني قدره $O (V 3)$ .

قاعدة اختيار إعادة التسمية إلى المقدمة

تقوم خوارزمية إعادة التسمية من البداية إلى النهاية ^{[ 1 ]} بتنظيم جميع العقد في قائمة مرتبطة، مع الحفاظ على الترتيب الطوبولوجي للقائمة بالنسبة للشبكة المسموح بها. تفحص الخوارزمية القائمة من البداية إلى النهاية، وتُجري عملية إزالة للعقدة الحالية إذا كانت نشطة. إذا أُعيدت تسمية العقدة، تُنقل إلى بداية القائمة، ويُعاد الفحص من البداية.

كما أن للخوارزمية تعقيدًا زمنيًا قدره $O (V 3) .$

قاعدة اختيار أعلى تصنيف

تقوم خوارزمية الدفع وإعادة التسمية ذات التصنيف الأعلى ^{[ 11 ]} بتنظيم جميع العقد في مجموعات مُفهرسة حسب تصنيفاتها. وتختار الخوارزمية دائمًا عقدة نشطة ذات تصنيف أعلى لتفريغها.

الخوارزمية لديها $O(V^{2}{\sqrt {E}})$ التعقيد الزمني. إذا تم استخدام قاعدة اختيار التصنيف الأدنى بدلاً من ذلك، يصبح التعقيد الزمني $O (V 2 E)$ . ^{[ 3 ]}

تقنيات التنفيذ

على الرغم من أنه في وصف خوارزمية الدفع وإعادة التسمية العامة أعلاه، يتم تعيين $𝓁(u)$ إلى الصفر لكل عقدة u باستثناء $s$ و $t$ في البداية، إلا أنه من الأفضل إجراء بحث عكسي بالعرض أولاً من $t$ لحساب التسميات الدقيقة. ^{[ 2 ]}

عادةً ما تُقسّم الخوارزمية إلى مرحلتين. في المرحلة الأولى، تُحسب أقصى تدفق مسبق عن طريق تفريغ العقد النشطة فقط التي تقلّ علاماتها عن $n$ . أما في المرحلة الثانية، فيُحوّل أقصى تدفق مسبق إلى أقصى تدفق عن طريق إعادة التدفق الزائد الذي لا يمكن أن يصل إلى $t$ إلى $s$ . يمكن إثبات أن المرحلة الثانية لها تعقيد زمني $O (VE)$ بغض النظر عن ترتيب عمليات الدفع وإعادة التسمية، وبالتالي فهي أقل تعقيدًا من المرحلة الأولى. بدلاً من ذلك، يمكن تنفيذها باستخدام تجزئة التدفق. ^{[ 9 ]}

تُعدّ الطرق الاستدلالية أساسية لتحسين الأداء التجريبي للخوارزمية. ^{[ 12 ]} من الطرق الاستدلالية الشائعة الاستخدام: طريقة الفجوة وطريقة إعادة التسمية الشاملة. ^{[ 2 ]}^{[ 13 ]} تكشف طريقة الفجوة عن الفجوات في دالة التسمية. إذا وُجدت تسمية 0 < 𝓁 ' < | V | لا يوجد لها عقدة $u$ بحيث $𝓁(u) = 𝓁'$ ، فإن أي عقدة $u$ تحقق $𝓁' < 𝓁(u) < | V |$ تكون منفصلة عن $t$ ويمكن إعادة تسميتها إلى $(| V | + 1)$ فورًا. تُجري طريقة إعادة التسمية الشاملة بحثًا دوريًا بالعرض أولًا عكسيًا من $t$ في $Gf لحساب التسميات الدقيقة للعقد .$ تتجاهل كلتا الطريقتين عمليات إعادة التسمية غير المفيدة، والتي تُشكّل عنق زجاجة للخوارزمية وتُساهم في عدم فعالية الأشجار الديناميكية. ^{[ 4 ]}

نماذج تطبيقية

تنفيذ بلغة C

#include <stdlib.h> #include <stdio.h>#define NODES 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000void push ( const int * const * C , int ** F , int * excess , int u , int v ) { int send = MIN ( excess [ u ], C [ u ][ v ] - F [ u ][ v ]); F [ u ][ v ] += send ; F [ v ][ u ] -= send ; excess [ u ] -= send ; excess [ v ] += send ; }void relabel ( const int * const * C , const int * const * F , int * height , int u ) { int v ; int min_height = INFINITE ; for ( v = 0 ; v < NODES ; v ++ ) { if ( C [ u ][ v ] - F [ u ][ v ] > 0 ) { min_height = MIN ( min_height , height [ v ]); height [ u ] = min_height + 1 ; } } };void discharge ( const int * const * C , int ** F , int * excess , int * height , int * seen , int u ) { while ( excess [ u ] > 0 ) { if ( seen [ u ] < NODES ) { int v = seen [ u ]; if (( C [ u ][ v ] - F [ u ][ v ] > 0 ) && ( height [ u ] > height [ v ])) { push ( C , F , excess , u , v ); } else { seen [ u ] += 1 ; } } else { relabel ( C , F , height , u ); seen [ u ] = 0 ; } } }void moveToFront ( int i , int * A ) { int temp = A [ i ]; int n ; for ( n = i ; n > 0 ; n -- ) { A [ n ] = A [ n -1 ]; } A [ 0 ] = temp ; }int pushRelabel ( const int * const * C , int ** F , int source , int sink ) { int * excess , * height , * list , * seen , i , p ;تم تخصيص الذاكرة للعقد باستخدام الدالة calloc . تم تخصيص الذاكرة للعقد باستخدام الدالة calloc . تم تخصيص الذاكرة للعقد باستخدام الدالة calloc . تم تخصيص الذاكرة للعقد باستخدام الدالة calloc .list = ( int * ) calloc (( NODES - 2 ), sizeof ( int ));for ( i = 0 , p = 0 ; i < NODES ; i ++ ){ if (( i != source ) && ( i != sink )) { list [ p ] = i ; p ++ ; } }الارتفاع [ المصدر ] = العقد ؛ الزيادة [ المصدر ] = لانهائي ؛ من أجل ( i = 0 ؛ i < العقد ؛ i ++ ) دفع ( C ، F ، الزيادة ، المصدر ، i )؛p = 0 ; while ( p < NODES - 2 ) { int u = list [ p ]; int old_height = height [ u ]; discharge ( C , F , excess , height , seen , u ); if ( height [ u ] > old_height ) { moveToFront ( p , list ); p = 0 ; } else { p += 1 ; } } int maxflow = 0 ; for ( i = 0 ; i < NODES ; i ++ ) maxflow += F [ source ][ i ];مجاني ( قائمة )؛حر ( مرئي )؛ حر ( ارتفاع )؛ حر ( زائد )؛أعد قيمة maxflow ؛ }void printMatrix ( const int * const * M ) { int i , j ; for ( i = 0 ; i < NODES ; i ++ ) { for ( j = 0 ; j < NODES ; j ++ ) printf ( "%d \t " , M [ i ][ j ]); printf ( " \n " ); } }int main ( void ) { int ** flow , ** capacitys , i ; flow = ( int ** ) calloc ( NODES , sizeof ( int * )); capacitys = ( int ** ) calloc ( NODES , sizeof ( int * )); for ( i = 0 ; i < NODES ; i ++ ) { flow [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); capacitys [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); }// سعات الرسم البياني النموذجي [ 0 ][ 1 ] = 2 ؛ سعات [ 0 ][ 2 ] = 9 ؛ سعات [ 1 ][ 2 ] = 1 ؛ سعات [ 1 ][ 3 ] = 0 ؛ سعات [ 1 ][ 4 ] = 0 ؛ سعات [ 2 ][ 4 ] = 7 ؛ سعات [ 3 ][ 5 ] = 7 ؛ سعات [ 4 ][ 5 ] = 4 ؛printf ( "السعة: \n " ); printMatrix ( capacities );printf ( "الحد الأقصى للتدفق: \n %d \n " , pushRelabel ( capacitys , flow , 0 , 5 ));printf ( "التدفقات: \n " ); printMatrix ( flow );return 0 ; }

تطبيق بايثون

دالة إعادة التسمية إلى المقدمة ( C ، المصدر : عدد صحيح ، الوجهة : عدد صحيح ) -> عدد صحيح : """خوارزمية التدفق الأقصى للدفع وإعادة التسمية.""" n = طول ( C ) # C هي مصفوفة السعة F = [[ 0 ] * n for _ in range ( n )] # السعة المتبقية من u إلى v هي C[u][v] - F[u][v]الارتفاع = [ 0 ] * ن # ارتفاع العقدة الزائد = [ 0 ] * ن # التدفق إلى العقدة مطروحًا منه التدفق من العقدة المرئية = [ 0 ] * ن # الجيران المرئيون منذ آخر إعادة تسمية # قائمة انتظار العقدة nodelist = [ i for i in range ( n ) if i != source and i != sink ]دالة push ( u , v ): send = min ( extra [ u ], C [ u ][ v ] - F [ u ][ v ]) F [ u ][ v ] += send F [ v ][ u ] -= send extra [ u ] -= send extra [ v ] += sendدالة إعادة التسمية ( u ): # إيجاد أصغر ارتفاع جديد يسمح بالدفع، # إن كان هذا الدفع ممكنًا أصلًا. min_height = ∞ for v in range ( n ): if C [ u ][ v ] - F [ u ][ v ] > 0 : min_height = min ( min_height , height [ v ]) height [ u ] = min_height + 1دالة التفريغ ( u ): طالما أن الزيادة [ u ] > 0 : إذا كان العنصر المرئي [ u ] < n : # تحقق من الجار التالي v = العنصر المرئي [ u ] إذا كان C [ u ][ v ] - F [ u ][ v ] > 0 و الارتفاع [ u ] > الارتفاع [ v ]: ادفع ( u , v ) وإلا : العنصر المرئي [ u ] += 1 وإلا : # لقد تحققنا من جميع الجيران. يجب إعادة التسمية relabel ( u ) العنصر المرئي [ u ] = 0الارتفاع [ المصدر ] = n # أطول مسار من المصدر إلى المصب أقل من n فائض طويل [ المصدر ] = ∞ # إرسال أكبر قدر ممكن من التدفق إلى جيران المصدر for v in range ( n ): push ( source , v )p = 0 بينما p < len ( nodelist ): u = nodelist [ p ] old_height = height [ u ] discharge ( u ) إذا كان height [ u ] > old_height : nodelist.insert ( 0 , nodelist.pop ( p ) ) # الانتقال إلى بداية القائمة p = 0 # البدء من بداية القائمة وإلا : p += 1أعد مجموع ( F [ المصدر ])

تطبيق R {base}

# (HL) خوارزمية التدفق الأقصى للدفع وإعادة التسمية. # قاعدة اختيار العقدة النشطة: أعلى تسمية. # R {الأساس}.push <- function ( u , v ) { d <- min ( excess [ u ], rGraph [ u , v ]) rGraph [ u , v ] <<- rGraph [ u , v ] - d # حافة أمامية، لا يوجد تدفق. rGraph [ v , u ] <<- rGraph [ v , u ] + d # حافة خلفية، تدفق موجه سابقًا، excess [ u ] <<- excess [ u ] - d # يمكن التراجع عنه. excess [ v ] <<- excess [ v ] + d pushCtr <<- pushCtr + 1L stopifnot ( pushCtr <= nV ^ 2 * sqrt ( nE )) }إعادة التسمية <- دالة ( u ) { الارتفاع [ u ] <<- الارتفاع [ u ] + 1L مركز إعادة التسمية <<- مركز إعادة التسمية + 1L }# تفريغ الرأس u ≠ {s, t} عبر الرسم البياني للشبكة المتبقية. # يُسمى الضلع (u, v) مقبولًا إذا كان ارتفاع[u] يساوي ارتفاع[v] + 1. تفريغ <- دالة ( u ) { الجيران <- أي ( rGraph [ u , ] > 0 ) مقبول <- الجيران [ أي ( ارتفاع [ u ] يساوي ارتفاع [ الجيران ] + 1L )] لـ ( v في مقبول ) { دفع ( u , v ) إذا ( زيادة [ u ] == 0 ) توقف } إذا ( زيادة [ u ] > 0 ) إعادة تسمية ( u ) }# التدفق المسبق: تدفق مع تخفيف قيود الحفظ: التدفق الداخل ≥ التدفق الخارج. # انقل التدفق الزائد عبر الحواف المسموح بها باتجاه المصب. # البيانات العامة: eCap، rGraph، الفائض، الارتفاع. مفهرسة بمعرف الرأس بدءًا من 1. pushRelabel <- function ( source , sink ) { rGraph <<- eCap # الرسم البياني المتبقي للشبكة. excess <<- # التدفق الداخل ناقص التدفق الخارج (≥ 0). height <<- rep ( 0L , nV ) # قيمة التسمية (𝓁).الارتفاع [ المصدر ] <<- nV الزيادة [ المصدر ] <<- Inf relabCtr <<- pushCtr <<- 0L # عد إعادة التسمية، الدفع.# ادفع الفائض من المصدر. sourceOut <- which ( rGraph [ source , ] > 0 ) for ( i in sourceOut ) push ( source , i )# الحلقة الرئيسية. حدد أعلى تصنيف ذي فائض موجب، # من جميع العقد باستثناء المصدر والمصب، ثم قم بالتفريغ. nlist <- setdiff ( seq ( from = 1 , to = nV , by = 1 ), c ( source , sink )) while (( active <- nlist [ which ( excess [ nlist ] > 0 )]) |> length () > 0 ) { u <- active [ which ( height [ active ] == max ( height [ active ]))][ 1 ] discharge ( u ) } # تم إرسال كل التدفق الزائد إلى المصب. return ( sum (( eCap - rGraph )[ source , ])) }# رسم بياني للبطولة، n = 4، أقصى تدفق = n - 1. eCap <- matrix ( 1L , 4 , 4 ); diag ( eCap ) <- 0L colnames ( eCap ) <- c ( "s" , seq ( 2 , length.out = ncol ( eCap ) - 2 ), "t" ) # المصدر هو 1، والمصب هو n. print ( list ( "مصفوفة السعة" = eCap ), max = 1600 )# حساب أقصى تدفق بين المصدر والمصب. nV <- ncol ( eCap ) # الرؤوس. nE <- sum ( eCap > 0 ) # الحواف. system.time ( maxFlow <- pushRelabel ( source = 1L , sink = nV )) print ( paste ( "VE =" , nV , nE , "maxFlow =" , maxFlow )) print ( paste ( "Relabel =" , relabCtr , "Push =" , pushCtr ))# تحقق، مصفوفة التدفق متناظرة عكسيًا. # تحقق، التدفق الخارج من المصدر (=1) يساوي التدفق الداخل إلى المصب (=nV). flow <- eCap - rGraph stopifnot (((( flow ) == - t ( flow )) |> all ())) stopifnot ( rowSums ( flow )[ 1 ] == colSums ( flow )[ nV ])# مصفوفة التجاور الموزونة للرسم البياني النهائي لشبكة التدفق الأقصى. mxFlow <- pmax ( flow , 0 ) print ( list ( "Residual network graph" = rGraph )) print ( list ( "Maximum flow" = mxFlow ))

انظر أيضاً

ملاحظات المحاضرة تيم رافغاردن ، دورة ثانية في الخوارزميات (CS261، شتاء 2016) ، جامعة كولومبيا، نيويورك.

مراجع

1 2 3 كورمين, تايلاند ; الأماكن القريبة : الأماكن القريبة : شتاين، سي. (2001). “§26 الحد الأقصى للتدفق”. مقدمة للخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ص 643 – 698. رقم ISBN 978-0262032933.
1 2 3 4 5 6 7 غولدبيرغ، أ. ف.؛ تارجان، ر. إ. (1986). "مقاربة جديدة لمسألة التدفق الأقصى". وقائع الندوة السنوية الثامنة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '86 . ص 136. doi : 10.1145/12130.12144 . ISBN 978-0897911931. S2CID 14492800 .
1 2 أهوجا، رافيندرا ك.؛ كوديالام، مورالي؛ ميشرا، أجاي ك.؛ أورلين، جيمس ب. (1997). "دراسات حسابية لخوارزميات التدفق الأقصى". المجلة الأوروبية لبحوث العمليات . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016/S0377-2217(96)00269-X .
1 2 3 غولدبيرغ، أندرو ف. (2008). "خوارزمية التوسيع الجزئي وإعادة التسمية لمسألة التدفق الأقصى". الخوارزميات - ESA 2008. سلسلة محاضرات في علوم الحاسوب. المجلد 5193. الصفحات 466-477 . CiteSeerX 10.1.1.150.5103 . doi : 10.1007/978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.
↑ غولدبيرغ، أندرو ف. (1997). "تنفيذ فعال لخوارزمية تدفق التكلفة الدنيا القابلة للتوسع". مجلة الخوارزميات . 22 : 1-29 . doi : 10.1006/jagm.1995.0805 .
↑ أهوجا، رافيندرا ك.؛ أورلين، جيمس ب. (1991). "خوارزميات المسار المعزز الموجهة بالمسافة لمسائل التدفق الأقصى ومسائل التدفق الأقصى البارامتري". بحوث اللوجستيات البحرية . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi : 10.1002/1520-6750(199106)38:3 < 413::AID-NAV3220380310 > 3.0.CO ; 2-J .
1 2 3 4 5 6 غولدبيرغ، أندرو ف.؛ تارجان، روبرت إي. (1988). "مقاربة جديدة لمسألة التدفق الأقصى" . مجلة ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID 52152408 .
↑ غولدبيرغ، أندرو ف.؛ تارجان، روبرت إي. (2014). "خوارزميات التدفق الأقصى الفعالة". اتصالات رابطة مكائن الحوسبة . 57 (8): 82. doi : 10.1145/2628036 . S2CID 17014879 .
1 2Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications (1st ed.). Prentice Hall. ISBN 978-0136175490.
↑Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n2log n) parallel max-flow algorithm". Journal of Algorithms. 3 (2): 128–146. doi:10.1016/0196-6774(82)90013-X.
↑Cheriyan, J.; Maheshwari, S. N. (1988). "Analysis of preflow push algorithms for maximum network flow". Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 338. p. 30. doi:10.1007/3-540-50517-2_69. ISBN 978-3-540-50517-4.
↑Cherkassky, Boris V.; Goldberg, Andrew V. (1995). "On implementing push-relabel method for the maximum flow problem". Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. Vol. 920. p. 157. CiteSeerX 10.1.1.150.3609. doi:10.1007/3-540-59408-6_49. ISBN 978-3-540-59408-6.
↑Derigs, U.; Meier, W. (1989). "Implementing Goldberg's max-flow-algorithm ? A computational investigation". Zeitschrift für Operations Research. 33 (6): 383. doi:10.1007/BF01415937. S2CID 39730584.

[clrs26-1] 1 2 3 كورمين, تايلاند ; الأماكن القريبة : الأماكن القريبة : شتاين، سي. (2001). “§26 الحد الأقصى للتدفق”. مقدمة للخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ص 643 – 698. رقم ISBN 978-0262032933.

[goldberg86-2] 1 2 3 4 5 6 7 غولدبيرغ، أ. ف.؛ تارجان، ر. إ. (1986). "مقاربة جديدة لمسألة التدفق الأقصى". وقائع الندوة السنوية الثامنة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '86 . ص 136. doi : 10.1145/12130.12144 . ISBN 978-0897911931. S2CID 14492800 .

[ahuja97-3] 1 2 أهوجا، رافيندرا ك.؛ كوديالام، مورالي؛ ميشرا، أجاي ك.؛ أورلين، جيمس ب. (1997). "دراسات حسابية لخوارزميات التدفق الأقصى". المجلة الأوروبية لبحوث العمليات . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016/S0377-2217(96)00269-X .

[goldberg08-4] 1 2 3 غولدبيرغ، أندرو ف. (2008). "خوارزمية التوسيع الجزئي وإعادة التسمية لمسألة التدفق الأقصى". الخوارزميات - ESA 2008. سلسلة محاضرات في علوم الحاسوب. المجلد 5193. الصفحات 466-477 . CiteSeerX 10.1.1.150.5103 . doi : 10.1007/978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.

[goldberg97-5] غولدبيرغ، أندرو ف. (1997). "تنفيذ فعال لخوارزمية تدفق التكلفة الدنيا القابلة للتوسع". مجلة الخوارزميات . 22 : 1-29 . doi : 10.1006/jagm.1995.0805 .

[ahuja91-6] أهوجا، رافيندرا ك.؛ أورلين، جيمس ب. (1991). "خوارزميات المسار المعزز الموجهة بالمسافة لمسائل التدفق الأقصى ومسائل التدفق الأقصى البارامتري". بحوث اللوجستيات البحرية . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi : 10.1002/1520-6750(199106)38:3 < 413::AID-NAV3220380310 > 3.0.CO ; 2-J .

[goldberg88-7] 1 2 3 4 5 6 غولدبيرغ، أندرو ف.؛ تارجان، روبرت إي. (1988). "مقاربة جديدة لمسألة التدفق الأقصى" . مجلة ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID 52152408 .

[goldberg2014-8] غولدبيرغ، أندرو ف.؛ تارجان، روبرت إي. (2014). "خوارزميات التدفق الأقصى الفعالة". اتصالات رابطة مكائن الحوسبة . 57 (8): 82. doi : 10.1145/2628036 . S2CID 17014879 .

[amo93-9] 1 2Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications (1st ed.). Prentice Hall. ISBN 978-0136175490.

[sv82-10] Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n2log n) parallel max-flow algorithm". Journal of Algorithms. 3 (2): 128–146. doi:10.1016/0196-6774(82)90013-X.

[cheriyan88-11] Cheriyan, J.; Maheshwari, S. N. (1988). "Analysis of preflow push algorithms for maximum network flow". Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 338. p. 30. doi:10.1007/3-540-50517-2_69. ISBN 978-3-540-50517-4.

[cherkassky95-12] Cherkassky, Boris V.; Goldberg, Andrew V. (1995). "On implementing push-relabel method for the maximum flow problem". Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. Vol. 920. p. 157. CiteSeerX 10.1.1.150.3609. doi:10.1007/3-540-59408-6_49. ISBN 978-3-540-59408-6.

[derigs89-13] Derigs, U.; Meier, W. (1989). "Implementing Goldberg's max-flow-algorithm ? A computational investigation". Zeitschrift für Operations Research. 33 (6): 383. doi:10.1007/BF01415937. S2CID 39730584.

[ 1 ]

[

3

4

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]