Онлайн кратчайший путь в заказанном отличии
-
29-09-2020 - |
Вопрос
Предположим, у меня есть экологически взвешенный укорененный 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 $ На нижнем уровне графика?», ДажеПо мере добавления больше уровней.
Я не мог найти никаких исследований, адресовании этого вопроса.
Решение
Если я правильно понимаю вашу проблему, вы, вероятно, не нашли никаких исследований, потому что проблема легко решить.
Если я не пропустил что-то, вы хотите сохранить экологически взвешенный «слоистый» 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 $ .
Другие советы
Предположим, у вас есть длина кратчайших путей от корня на все узлы на уровне $ l_i $ и вызовите этот $ s \ in l_i \ to \ mathbb {z} $ .Теперь предположим, что края из $ l_i $ на $ l_ {i + 1} $ называются