نعم ، أنت محقتعمل خوارزمية Prim مثل خوارزمية dijkstra ولكن في خوارزمية prim لا ينبغي أن تحسب أقصر مسار من i إلى j لها حواف سالبة. لذا ، فإنهم خوارزمية أخرى هي خوارزمية بيلمان-فورد لحساب أقصر مسار من i إلى j بحافة سالبة.
لماذا تعمل خوارزمية Prim؟
في علوم الكمبيوتر ، خوارزمية Prim (المعروفة أيضًا باسم خوارزمية Jarník) هي خوارزمية جشعة تجد الحد الأدنى من الشجرة الممتدة لرسم بياني مرجح غير موجهوهذا يعني أنها تجد مجموعة فرعية من الحواف التي تشكل شجرة تتضمن كل رأس ، حيث يتم تقليل الوزن الإجمالي لجميع حواف الشجرة.
هل خوارزمية Prim صحيحة؟
إثبات الصحة
أثبتنا أن خوارزمية Prim صحيحة عن طريق الاستقراء على الشجرة المتنامية التي أنشأتها الخوارزمية. … نثبت عن طريق الانكماش أن Tiجزء من الحد الأدنى من الشجرة الممتدة. دع ei=(v، u) هي الحافة التي تم العثور عليها بواسطة خوارزمية Prim وافترض أنها ليست حافة الحد الأدنى للشجرة الممتدة.
ما مدى كفاءة خوارزمية Prim؟
تعمل خوارزمية Prim بكفاءة إذا احتفظنا بقائمة d [v] من أرخص الأوزان التي تربط الرأس ، v، غير الموجود في الشجرة ، بأي رأس بالفعل في الشجرة. …
هل يعمل Prims مع أوزان سلبية؟
هل بريم؟ الحل: نعم، كلا الخوارزميتين تعملان بأوزان سالبة للحافة لأن خاصية القطع لا تزال سارية.
