أقصر طريق عبر الإنترنت في DAG

Question

لنفترض أن لدي حافة مرجحة متصلة DAG $ g= (v، e، r \ in v، w \ in e \ to \ mathbb {z}) $ حيث يوجد تسلسل من مجموعات غير أساسية (تسمى "المستويات") $ l_0={r \}، l_1 \ subset v، \ ldots، l_n \ subset v $ مثل هذا $ l_0 \ cup \ ldots \ ldots \ cup l_n= v $ والحواف الصادرة للعقد في $L_I $ الاتصال فقط بالعقد في $ l_ {i + 1} $ .

هل هناك خوارزمية عبر الإنترنت التي يمكن أن تحتفظ بمجموعة من أقصر المسارات حيث يتم إضافة المزيد من المستويات إلى هذه DAG؟بمعنى آخر، يمكن أن تجيب على الاستعلام "ما هو الحد الأدنى من مسار الوزن من الجذر إلى بعض العقدة $ n $ في المستوى السفلي من الرسم البياني؟"، حتىيتم إضافة المزيد من المستويات.

لم أتمكن من العثور على أي بحث يتناول هذا السؤال.

Answer 1

إذا فهمت مشكلتك بشكل صحيح، فربما لم تجد أي بحث لأن المشكلة سهلة حلها.

ما لم أفتقد شيئا ما، فأنت تريد الحفاظ على "الطبقات" الطبقات "المرجح على الحافة=" حاوية الرياضيات "> $ g= (l_0، \ cup \ dots \ cup l_k، e) $ (كما هو محدد في سؤالك) ودعم العمليات التالية:

• init (): إنشاء رسم بياني مع طبقة واحدة فقط $ l_0 $ ، a vertex $ r \ في L_0 $ ، ولا حواف.

• query (): إرجاع $ \ min_ {v \ in l_k} d (r، v) $ .

• add_layer ( $ l_ {k + 1}، e '$ ): يتم إعطاؤك مجموعة جديدة $ l_ {k + 1} $ من القمم ومجموعة من الحواف المرجحة $ e '\ subseteq (l_k \ times l_ {k + 1}) $ . يتم تحديث مجموعة قمة الرأس من $ g $ "span class=" math-container "> $ l_0 \ cup \ ldots \ ldots \ cup l_k \ cup l_ {k + 1 } $ ومجموعة حافة من $ G $ يتم تحديثها إلى $ e \ cup e '$ .

يمكنك القيام بما سبتك من خلال تخزين: 1) لكل قمة الرأس $ v \ in l_k $ ، المسافة $ D [V] $ نموذج $ s $ to $ v $ في $ g $ ، و 2) الحد الأدنى للمسافة $ d ^ * $ من $ S $ إلى قمة المستوى الأخير.

مبالغ عملية النسوية لإعداد $ d [r]= 0 $ . لإجراء عملية الاستعلام فقط إرجاع $ d ^ * $ .

لتنفيذ add_layer ( $ l_ {k + 1}، e '$ )، تابع كما يلي:

• تعيين $ d ^ * $ إلى $ + \ enfty $ ،
• لكل قمة الرأس $ v \ in l_ {k + 1} $ :
  • تعيين $ d [v]= + \ enfty $
  • لكل حافة $ (u، v) $ في $ e '$ :
    • تحديث $ d [v] $ إلى $ \ min \ {d [v]، d [u] W (U، V) \} $
  • تحديث $ d ^ * $ إلى $ \ min \ {d ^ *، d [v] \}

لاحظ أن هذا يتطلب الوقت يتناسب مع $ | l_ {k + 1} | + | E '| $ ، وبالتالي فهي مثالية مقارنة. لاحظ أيضا أن هذا الحل لا يحتاج إلى تخزين $ g $ .

Answer 2

افترض أن لديك طول أقصر المسارات من الجذر إلى جميع العقد في المستوى $ l_i $ ، واتصل بهذا $ s \ in l_i \ to \ mathbb {z} $ .افترض الآن أن الحواف من $ l_i $ إلى $ l_ {i + 1} $ تسمى $ e_i $ .ثم طول أقصر الطريق إلى العقدة $ n $ في $ l_ {i + 1} $ يتم تعريفه بواسطة $ \ min \ {w (x، n) + s (x) \ mile (x، n) \ in e_i \} $ .الحفاظ على المسارات الفعلية هو امتداد سهل.