Online Kürzester Pfad in bestellter DAG

Question

Angenommen, ich habe eine kantengewichtete angeschlossene verwurzelte DAG $ g= (v, e, r \ in v, w \ in e \ to \ mathbb {z \ in e \ t \ mathbb {z}) wo es eine Reihenfolge nicht leererer Sätze gibt ("Pegel") $ l_0={r \}, l_1 \ Subset V, \ LDOTs, L_N \ Subset V $ so, dass $ l_0 \ cup \ ldots \ cup l_n= v $ und die ausgehenden Kanten der Knoten in $L_i $ Nur eine Verbindung zu Knoten in $ l_ {i + 1} $ .

Gibt es einen Online-Algorithmus, der einen Satz kürzester Wege aufrechterhalten kann, da zu diesem DAG mehr Ebenen hinzugefügt werden?Mit anderen Worten, es kann die Abfrage beantworten "Was ist der minimale Gewichtspfad von der Wurzel zu einigen Knoten $ n $ in der unteren Ebene der Grafik?",Da mehr Ebenen hinzugefügt werden.

Ich konnte keine Forschung finden, die diese Frage anspricht.

Answer 1

Wenn ich Ihr Problem richtig verstehe, dann haben Sie wahrscheinlich keine Forschung gefunden, da das Problem leicht zu lösen ist.

Wenn ich nichts verpasst habe, möchten Sie einen randgewichteten "geschichteten" DAG $ g= (l_0, \ cup \ dots \ cup l_k, e) $ (wie in Ihrer Frage definiert) und unterstützen die folgenden zwei Operationen:

.

• init (): Erstellen Sie ein Diagramm mit nur einer Ebene $ l_0 $ , einem einzelnen Scheitelpunkt $ r \ in l_0 $ und keine Kanten.

• abfrage (): return $ \ min_ {v \ in l_k} d (r, v) $ .

• add_layer ( $ l_ {k + 1}, E '$ ): Sie erhalten einen neuen Set $ L_ {k + 1} $ von Ecken und ein Satz von gewichteten Kanten $ E '\ Subseteq (l_k \ times l_ {k + 1}) $ . Der Scheitelpunkt von $ g $ wird auf $ l_0 \ cup \ ldots \ cup l_k \ cup l_ {k + 1 aktualisiert } $ und der Randsatz von $ g $ wird auf $ E \ Cup E '$ .

Sie können das oben genannte durchführen, indem Sie: 1) für jeden Scheitelpunkt $ v \ in l_k $ , die Entfernung $ D [v] $ Formular $ s $ bis $ V $ in $ G $ und 2) der Mindestabstand $ d ^ * $ aus $ s $ an einem Scheitelpunkt der letzten Ebene.

Der Init-Betrieb beläuft sich auf das Einstellen der $ D [R]= 0 $ . Um den Abfragevorgang auszuführen, rufen Sie einfach zurück $ d ^ * $ .

Zum Implementieren von add_layer ( $ l_ {k + 1}, e '$ ) fordern Sie wie folgt vor:

.
• Set $ d ^ * $ bis $ + \ Infty $ ,
• für jeden Vertex $ v \ in l_ {k + 1} $ :
  .
  • Set $ D [V]= + \ Infty $
  • Für jede Kante $ (u, v) $ in $ E '$ :
    .
    • update $ d [v] $ bis $ \ min \ {d [v], d [u] + w (u, v) \} $
  • update $ d ^ * $ bis $ \ min \ {d ^ *, d [v] \} $

Beachten Sie, dass dies Zeit erfordert, proportional zu $ | L_ {k + 1} | + | E '| $ und ist daher asymptotisch optimal. Beachten Sie auch, dass diese Lösung nicht $ G $ speichern muss.

Answer 2

Angenommen, Sie haben die Länge der kürzesten Wege von der Wurzel an alle Knoten in Level $ l_i $ , und rufen Sie diesen $ s \ in l_i \ to \ mathbb {z} $ .Nehmen Sie nun an, dass die Kanten von $ l_i $ bis $ l_ {i + 1} $ aufgerufen werdenKlasse="Math-Container"> $ E_i $ .Dann die Länge des kürzesten Pfads zu einem Knoten $ n $ in $ l_ {i + 1} $ ist definiert von $ \ min \ {w (x, n) + s (x) \ MID (x, n) \ in E_I \} $ .Die Aufrechterhaltung der tatsächlichen Pfade ist eine einfache Erweiterung.