ابحث عن أطول مسار في رسم بياني دوري موجه من مصدر إلى وجهة f. افترض عدم وجود دورات إيجابية للوزن

Question

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

شكرًا

Answer 1

لست متأكدًا مما إذا كان هذا سيعمل (بحاجة إلى التحقق من ذلك) ولكن ... يمكنك أن تفعل شيئًا مشابهًا لـ:

يترك min = min weight on the graph.
max = max weight on the graph.
تعيين أوزان جديدة لجميع الحواف = wNew(e) = max - (wOld(e)-min).

الآن هناك wights سلبية والأوزان في ترتيب عكسي (بمعنى إذا w(e1) كان أكبر من w(e2) إنه الآن أصغر).

ماذا لو بحثنا الآن عن أقصر مسار؟

Answer 2

ما عليك سوى نفي أوزان الحافة وتشغيل خوارزمية مسار أقصر (على سبيل المثال ، Bellman-Ford).

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

أنظر أيضا أطول مسار بين اثنين

Answer 3

إذا حصلت على DCG ، فيمكنك فقط حلقة إلى الأبد قبل أن تصل إلى هدفك ، فسيكون ذلك "أطول مسار". في هذه الحالة ، يكون السؤال غير مكتمل ، وربما تبدو الخوارزمية مختلفة اعتمادًا على التفاصيل.

هذا يبدو مثل الواجب المنزلي.