لماذا نقوم بالفرز الطوبولوجي للعثور على أقصر أو أطول مسار في DAG الموزون؟

Question

كنت أتساءل لماذا يتعين علينا القيام بالفرز الطوبولوجي قبل إجراء عملية إرخاء الحواف.

أليس من الأفضل أن نفعل :إذا كانت قمة البداية هي "s"

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

لقد تركت عمدًا المصفوفة التي تمت زيارتها[]

Answer 1

باستخدام هذه الخوارزمية لن يكون التعقيد الزمني المتوقع O(V+E) كما يتعين علينا زيارة حافة عدة مرات.

queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue

ولكن باستخدام الفرز الطوبولوجي، نحصل على الترتيب الذي يجب أن يتم به عبور القمم بحيث تتم زيارة الحافة مرة واحدة بالضبط.لذلك كان بإمكاننا ضمان T. C.ل O(V+E).

لذلك لحل هذه المشكلة للعمل فيها O(V+E) نحن نستخدم الفرز الطوبولوجي.

لكنني أعتقد أن هذا ليس كافيًا، يجب أن نعرف أيضًا سبب استخدام الترتيب الطوبولوجي هنا حتى يساعد في حل المشكلات الأخرى.

لماذا الترتيب الطوبولوجي؟

الترتيب الطوبولوجي يعطينا الترتيب مثل 0 1 2 3 4 5 ثم، بمجرد وصولنا إلى عقدة بهذا الترتيب (على سبيل المثال 4) ثم قمنا بالفعل بحساب أقصر طريق إليه (4) مثل كافة الحواف (وكذلك المسارات) للكتابة u -> v (v = 4) وقد تمت زيارتها بالفعل.