Онлайн кратчайший путь в заказанном отличии

Question

Предположим, у меня есть экологически взвешенный укорененный roted dag $ g= (v, e, r \ in v, w \ in \ to \ mathbb {z}) $ Где существует последовательность непустых наборов (называемых «уровнями») $ l_0={r \}, l_1 \ subset v, \ ldots, l_n \ подмножество v $ такой, что $ l_0 \ cup \ ldots \ cup l_n= v $ и исходящие края узлов в $L_i $ Подключаются только к узлам в $ l_ {I + 1} $ .

Есть ли онлайн алгоритм, который может поддерживать набор кратчайших путей, поскольку к этому DAG добавляется больше уровней?Другими словами, он может ответить на запрос «Что такое минимальный путь от корня до некоторого узла $ N $ На нижнем уровне графика?», ДажеПо мере добавления больше уровней.

Я не мог найти никаких исследований, адресовании этого вопроса.

Answer 1

Если я правильно понимаю вашу проблему, вы, вероятно, не нашли никаких исследований, потому что проблема легко решить.

Если я не пропустил что-то, вы хотите сохранить экологически взвешенный «слоистый» dag $ G= (L_0, \ CUP \ DOTS \ CUP L_K, E) $ (Как определено в вашем вопросе) и поддерживать следующие две операции:

.

• init (): создать график только с одним слоем $ l_0 $ , одна вершина $ R \ in l_0 $ , и нет ребер.

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

• add_layer ( $ l_ {k + 1}, e '$ ): Вам дан новый набор $ L_ {k + 1} $ вершин и набор взвешенных ребер $ E '\ SubsEtq (l_k \ manse l_ {k + 1}) $ . Набор вершин $ g $ обновляется до $ l_0 \ cup \ ldots \ cup l_k \ cup l_ {k + 1 } $ и краевой набор $ g $ обновляется до $ e \ Cup E '$ .

Вы можете сделать вышеизложенное, сохраняя: 1) для каждой вершины $ v \ in l_k $ , расстояние $ D [v] $ form $ s $ на $ v $ в $ G $ , и 2) минимальное расстояние $ d ^ * $ из $ s $ до вершины последнего уровня.

Операция init Сумма на настройку $ d [r]= 0 $ . Для выполнения операции запроса просто верните $ d ^ * $ .

Для реализации ADD_Layer ( $ l_ {k + 1}, e '$ ), вы действуете следующим образом:

.
• set $ d ^ * $ на $ + \ infty $ ,
• для каждой вершины $ v \ in l_ {k + 1} $ :
  .
  • set $ d [v]= + \ infty $
  • для каждого края $ (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) \ mid (x, n) \ in e_i \} $ .Поддержание фактических путей - это простое расширение.