الحد الأدنى لوزن الحافة على طول المسار

Question

كيف يمكنني العثور على الحد الأقصى لمجموعة من أوزان الحواف الدنيا على طول كل المسار الممكن بين القمم التعسفية (u,v)?

كنت أفكر في تعديل فلويد-وارشال؟

i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9

الحد الأدنى لوزن الحافة هو 1

Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7

الحد الأدنى لوزن الحافة هو 3

وهكذا تكون النتيجة max(1, 3) = 3

Answer 1

نعم، قد ينجح تعديل Floyd-Warshall - فبدلاً من أقصر طول للمسار، ستتتبع الحد الأقصى "لعرض" المسار.

إذا كنت مهتمًا برأسين فقط، فيمكنك اتباع نهج أبسط:ابدأ برسم بياني فارغ وأضف الحواف مرتبة حسب وزنها (من الأعلى إلى الأدنى).عندما يتم توصيل العقد المعنية، فإن الحافة الأخيرة المضافة تمنحك "العرض" الأقصى.تم بشكل صحيح (أي.باستخدام مجموعة مفككة للتحقق من الاتصال)، سيكون هذا أسرع من فلويد-وارشال.

ملحوظة:أنا أفكر فقط في الأوزان الإيجابية.