هل يستحق الأمر تقليم الرسم البياني كما هو مطلوب قبل تطبيق خوارزمية Dijkstra على ذلك؟

Question

أنا أستخدم خوارزمية Dijkstra في البرنامج. لنفترض أن لدي رسم بياني مع رؤوس وحواف. إذا تخيلنا أن جميع الحواف تبدأ من مصدر Vertex "أ" كما يلي

a-->b        
a-->c   and  
a-->d  

وجميع الحواف التي تنتهي إلى Vertex "F" نكون:

b-->f
m-->f
e-->f
w-->f

ما أحتاج إلى معرفته من البداية هو أنه أريد الحافة أ-> ب كحافة البداية الخاصة بي (افترض "أ" كنقطة بداية) لذلك لا تحتاج إلى البحث عن الجيران الآخرين "أ" بمعنى آخر (a-->c and a-->d)

كما أريد فقط المسارات التي تنتهي م-> و (يفترض "F" كوجهة) أي لا أريد المسار الذي يحتوي b-->f,m-->f,e-->f,w-->f

فهل من الجيد تقليم الرسم البياني الأولي الخاص بي لأنه لا يحتوي على هذه الحواف ثم تطبيق dijkstra على ذلك؟

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

Answer 1

لماذا لا تبحث فقط عن مسار من b إلى m ثم وأضف الحواف التي تريدها بعد ذلك؟ إذا كنت بحاجة إليها حقًا ، فيمكنك إضافة حالة خاصة لاستبعاد الحواف التي تحتوي على a و f من أي وقت مضى إضافته إلى المكدس - يجب عليك التحقق مما إذا كان ذلك يجعل الأمر أسرع بشكل عام ، فالرهني هو أنه سوف على الرسوم البيانية الصغيرة ولكن ليس على الرسوم البيانية حقًا (يتغير فقط السرعة بعامل ثابت على أي حال).