اقتراحات لـ KSPA على الرسم البياني غير الموجه

Question

هناك تطبيق مخصص لـ KSPA يحتاج إلى إعادة كتابته.يستخدم التطبيق الحالي خوارزمية Dijkstra المعدلة والتي تم شرح الكود الكاذب الخاص بها تقريبًا أدناه.ومن المعروف باسم KSPA باستخدام استراتيجية حذف الحافة على ما أعتقد.(أنا مبتدئ في نظرية الرسم البياني).

Step:-1.  Calculate the shortest path between any given pair of nodes using the Dijkstra algorithm. k = 0 here.
Step:-2.   Set k = 1
Step:-3.   Extract all the edges from all the ‘k-1’ shortest path trees. Add the same to a linked list Edge_List.
Step:-4.  Create a combination of ‘k’ edges from Edge_List to be deleted at once such that each edge belongs to a different SPT (Shortest Path Tree). This can be done by inspecting the ‘k’ value for each edge of the combination considered. The ‘k’ value has to be different for each of the edge of the chosen combination.
Step:-5.   Delete the combination of edges chosen in the above step temporarily from the graph in memory.
Step:-6.   Re-run Dijkstra for the same pair of nodes as in Step:-1.
Step:-7.   Add the resulting path into a temporary list of paths. Paths_List.
Step:-8.   Restore the deleted edges back into the graph.
Step:-9.   Go to Step:-4 to get another combination of edges for deletion until all unique combinations are exhausted. This is nothing but choosing ‘r’ edges at a time among ‘n’ edges => nCr.
Step:-10. The ‘k+1’ th shortest path is = Minimum(Paths_List).
Step:-11. k = k + 1 Go to Step:-3, until k < N.
Step:-12. STOP

كما أفهم الخوارزمية، للحصول على أقصر مسار k، يجب العثور على SPTs "k-1" بين كل زوج وجهة المصدر وحواف "k-1" من كل SPT واحد يجب حذفها في وقت واحد لكل مجموعة.من الواضح أن هذه الخوارزمية لها تعقيد اندماجي وتعوق عمل الخادم في الرسوم البيانية الكبيرة.اقترح عليّ الناس خوارزمية إبشتاين (http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf).لكن هذه الورقة البيضاء تستشهد بـ "digraphs" ولم أر إشارة إلى أنها تعمل فقط مع digraphs.أردت فقط أن أسأل الناس هنا إذا كان أي شخص قد استخدم هذه الخوارزمية على رسم بياني غير موجه؟

إذا لم يكن الأمر كذلك، فهل هناك خوارزميات جيدة (من حيث التعقيد الزمني) لتنفيذ KSPA على رسم بياني غير موجه؟

شكرا لك مقدما،

Answer 1

تعقيد الوقت:O(K*(E*log(K)+V*log(V)))

تعقيد الذاكرة لـ O(K*V) (+O(E) لتخزين الإدخال).

نقوم بإجراء Djikstra المعدلة على النحو التالي:

• لكل عقدة، بدلاً من الاحتفاظ بأفضل تكلفة معروفة حاليًا للمسار من عقدة البداية.نحن نحتفظ بأفضل طرق K من عقدة البداية
• عند تحديث العقد المجاورة، لا نتحقق مما إذا كانت تعمل على تحسين أفضل مسار معروف حاليًا (كما يفعل Djikstra)، بل نتحقق مما إذا كانت تعمل على تحسين أسوأ مسار معروف حاليًا لـ K.
• بعد أن قمنا بالفعل بمعالجة أول مسارات K للعقد، لا نحتاج إلى العثور على أفضل مسارات K، ولكن يتبقى لدينا K-1 فقط، وبعد K-2 آخر.هذا ما أسميه K'.
• بالنسبة لكل عقدة، سنحتفظ بقائمة انتظار ذات أولوية لأطوال المسارات المعروفة حاليًا لـ K.
  • في إحدى قوائم الانتظار ذات الأولوية، يكون أقصر مسار في الأعلى.نحن نستخدم قائمة انتظار الأولوية هذه لتحديد أي من K' هو الأفضل وسيتم استخدامه في قوائم انتظار أولوية Djikstra العادية كممثل للعقدة.
  • وفي قائمة الانتظار ذات الأولوية الأخرى، يوجد المسار الأطول في الأعلى.نحن نستخدم هذا لمقارنة المسارات المرشحة بأسوأ مسارات K.