Dijkstra أقصر خوارزمية مسار مع تكلفة الحافة

Question

لدي رسم بياني موجه مرجح إيجابي. كل حافة لها تكلفة الاستخدام. ليس لدي سوى أموال ، أريد حساب أقصر المسارات باستخدام خوارزمية Dijkstra ، ولكن يجب أن يكون مجموع تكاليف الحواف على الطريق أقل أو مساوية لـ A.

أريد أن أفعل ذلك بأكثر تعديل Dijstra الأصغر (إذا كان بإمكاني القيام بذلك مع تعديل صغير لـ Dijkstra). يجب أن أفعل هذا في O(n*log(n)) إذا استطعت ، لكنني أعتقد أنني أستطيع ذلك.

هل من أحد يستطيع مساعدتي في هذا؟

Answer 1

https://www.spoj.pl/prombs/roads/

تم تقديم المشكلة في الرئيس التنفيذي '98 ويمكن العثور على حلها الرسمي هنا.

Answer 2

لا تحتاج حقًا إلى تعديل خوارزمية Dijkstra للقيام بذلك لأن الإجابة تعادل إيجاد أقصر مسار ثم قبوله إذا كان أقل من أو يساوي A.

بالطبع ، يمكنك دائمًا أن تقصر الحلقة الداخلية إذا قمت بزيارة مسار بتكلفة أكثر من A.

تحرير: مع التوضيح الذي تريد تقليل التكلفة والمسافة ، لا يمكنك القيام بذلك دون توضيح الحل الذي تريده. هل تريد أرخص مسار؟ هل تريد أقصر مسار؟ هل تريد بعض وظائف التكلفة والمسافة؟ كل هذه تحدد وظيفة الترجيح التي يجب استخدامها لحافة معينة.