إثبات أن قيم المسافة المستخرجة في خوارزمية Dijkstra غير تنقلب؟

Question

أنا أراجع ملاحظات الخوارزميات القديمة الخاصة بي وقد واجهت هذا الدليل. لقد كان من المهمة التي أجريتها وحصلت عليها ، لكنني أشعر أن الدليل يفتقر بالتأكيد.

السؤال هو prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

يذهب برهاني على النحو التالي:

إثبات التناقض. قبضة ، افترض أننا نسحب قمة من Q مع قيمة d 'i'. في المرة القادمة ، نسحب رأسًا مع قيمة D 'J'. عندما سحبنا أنا ، قمنا بإنهاء قيمة D وحساب أقصر المسار من قمة البداية ، S ، إلى أنا. نظرًا لأن لدينا أوزان إيجابية ، فمن المستحيل أن تتقلص قيم D لدينا ونحن نضيف رؤوسًا إلى مسارنا. إذا بعد سحبها من Q ، نسحب J بقيمة D أصغر ، فقد لا يكون لدينا أقصر مسار إلى I ، لأننا قد نتمكن من الوصول إلى I إلى J. ومع ذلك ، فقد قمنا بالفعل بحساب أقصر مسار إلى أنا. لم نتحقق من مسار ممكن. لم يعد لدينا مسار مضمون. تناقض.

كيف يمكن تحسين هذا الدليل؟ أو الأفضل من ذلك ، هل هناك نهج مختلف؟ يبدو فقط ضعيفًا جدًا :)

تعديل: آسف ، في هذه الحالة ، يتم تنفيذ قائمة انتظار أولويتي باستخدام مين

Answer 1

دعونا نؤسس هذه (هذه كلها صحيحة ، لأنها ، في الأساس ، تعريف الخوارزمية):

1. ستمنحك قائمة انتظار الأولوية في خوارزمية Dijkstra العقدة بأقل قيمة D في كل تكرار للخوارزمية.
2. لا توجد أوزان حافة سلبية.
3. بمجرد إزالة العقدة ، لن تعود أبدًا إلى قائمة الانتظار.
4. القيمة d للعقدة التي تم إلغاؤها هي نهائية ، ولن تتغير من تلك النقطة فصاعدًا.

المستمر (1) ، القيمة d لتلك العقدة المزعجة ، على افتراض (2) ، ستكون على الأقل مساوية للقيمة D السابقة المستخرجة ، لأن قيمة كل عقدة تعتمد على قيم D للعقد Dequeed قبل ذلك ، وهو نوع من التعريف العودية. نظرًا لأن (3) و (4) صحيحة ، ينتهي هذا التعريف المتكرر في عقدة البداية التي تحتوي على قيمة D من 0.
لذلك ، إذا كانت قيمة كل عقدة على الأقل مساوية للقيمة D التي أمامه ، ولا تزال (1) تنطبق ، مجموعة القيم D المستخرجة من قائمة انتظار الأولوية غير ينقلب.

(بعد القراءة من خلال هذا ، وما كتبته ، إنه نفس الشيء ، لكنه قدم أفضل قليلاً على ما أعتقد)