صحة خوارزمية بيلمان فورد، هل لا يزال بإمكاننا القيام به بشكل أفضل؟

Question

تعلمت أن خوارزمية Bellman-Ford لها وقت تشغيل O (| E | * | v |)، والتي يكون فيها E عدد الحواف و V، عدد القمم.افترض أن الرسم البياني ليس لديه أي دورات سلبية مرجحة.

سؤالي الأول هو أن نثبت أنه في الداخل (| V | -1) التكرارات (يتحقق كل تكرار كل حافة في ه)، فإنه يقوم بتحديث أقصر طريق إلى كل عقدة ممكنة، بالنظر إلى عقدة بداية معينة؟هل من الممكن أن يتم تكرارا (| الخامس | -1) مرات ولكن لا يزال لا ينتهي بأقصر المسارات لكل عقدة؟

تفترض صحة الخوارزمية، هل يمكننا فعلا أن نفعل ذلك أفضل من ذلك؟يحدث لي أن لا يتم وزن جميع الحواف سلبا في رسم بياني معين.تبدو خوارزمية Bellman-Ford باهظة الثمن، حيث أن كل تكرار يمر عبر كل حواف.

Answer 1

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

هذا التعقيد ضيق (على الأقل ل BF)، فكر في خط طويل من القمم المتصلة. اختر أقصى اليسار كمصدر - سيتعين على عملية التحديث الخاصة بك أن تعمل طريقها من هناك إلى الجانب الآخر بمجرد القيادة في وقت واحد. الآن قد تجادل بأنك لا تضطر إلى التحقق من كل حافة بهذه الطريقة، لذلك دعونا نرمي في عدد قليل من الحواف العشوائية مع وزن كبير جدا (N> | V | * ماكس الوزن) - لا يمكنهم مساعدتك، ولكن لا يمكن أن تعرف الخوارزمية الخاصة بك بالتأكيد، لذلك إذا كان يجب أن تذهب من خلال عملية تحديث القمم بهذه الأوزان (لا تزال أفضل من اللانهاية الأولي).