مشكلة كبيرة مع خوارزمية Dijkstra في تطبيق الرسم البياني المرتبط

Question

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

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

ليس لدي وقت لتغيير تنفيذ الرسم البياني الخاص بي ، لكن لدي جدول تجزئة ، فهرسته برقم فريد (ولكن لا يبدأ من 0 ، إنه مثل 100090000) وهي المشكلة التي أواجهها. كلما احتجت ، أستخدم مشغل Modulo للحصول على رقم بين 0 وإجمالي عدد القمم.

يعمل هذا بشكل جيد عندما أحتاج إلى فهرس صفيف من الرقم ، ولكن عندما أحتاج إلى الرقم من فهرس الصفيف (للوصول إلى قمة المسافة الدنيا المحسوبة في وقت ثابت) ، وليس كثيرًا.

حاولت البحث عن كيفية عكس عملية Modulo ، مثل ، 100090000 mod 18000 = 10000 ، و 10000 invmod 18000 = 100090000 ولكن لم أتمكن من العثور على طريقة للقيام بذلك.

البديل التالي هو إنشاء نوع من الصفيف المرجعي حيث ، في المثال أعلاه ، ARR [10000] = 100090000. من شأنه أن يحل المشكلة ، ولكن سيتطلب حلقة الرسم البياني بالكامل مرة أخرى.

هل لدي حل أفضل/أسهل مع تطبيق الرسم البياني الحالي الخاص بي؟

Answer 1

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