Caminho mais curto on-line em ordem ordenada

Question

Suponha que eu tenha uma Dag enraizada conectada ponderada à borda $ g= (v, e, r \ in v, w \ in e \ to mathbb {z}) $ onde existe uma sequência de conjuntos não fixos (chamados de "níveis") $ l_0= {r \}, l_1 \ subset v, \ ldots, l_n \ subset v $ tal que $ l_0 \ cope \ ldots \ cope l_n= v $ e as bordas de saída dos nós na $L_I $ Conecte-se apenas a nós na $ l_ {i + 1} $ .

Existe um algoritmo on-line que pode manter um conjunto de caminhos mais curtos à medida que mais níveis são adicionados a este DAG?Em outras palavras, pode responder à consulta "Qual é o caminho mínimo de peso da raiz para um nó $ n $ no nível inferior do gráfico?", MesmoÀ medida que mais níveis são adicionados.

Não consegui encontrar nenhuma pesquisa abordando esta pergunta.

Answer 1

Se eu entender seu problema corretamente, você provavelmente não encontrou nenhuma pesquisa porque o problema é fácil de resolver.

A menos que eu tenha perdido alguma coisa, você quer manter um "camadas" de camadas de borda "camadas", recipiente de matemática "> $ g= (l_0, \ cope \ dots \ cope l_k, e) $ (conforme definido em sua pergunta) e apoie as duas operações a seguir:

• init (): criar um gráfico com apenas uma camada $ l_0 $ , um único vértice $ r \ in l_0 $ e sem arestas.

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

• add_layer ( $ l_ {k + 1}, e '$ ): você recebe um novo conjunto $ L_ {k + 1} $ de vértices e um conjunto de bordas ponderadas $ e '\ subseteq (l_k \ vezes l_ {k + 1}) $ . O conjunto de vértice de $ g $ é atualizado para $ l_0 \ copo \ l_k \ cope l_ {k + 1 } $ e o conjunto de borda de $ g $ é atualizado para $ e \ cope e '$ .

Você pode fazer o acima armazenando: 1) Para cada vértice $ v \ in l_k $ , a distância $ D [v] $ formulário $ s $ para $ v $ em $ g $ e 2) a distância mínima $ d ^ * $ da $ s $ para um vértice do último nível.

A operação de inicialização é montante para definir $ D [R]= 0 $ . Para executar a operação de consulta basta retornar $ d ^ * $ .

Para implementar add_layer ( $ l_ {k + 1}, e '$ ), você procede da seguinte forma:

• set $ D ^ * $ para $ + \ Fgrty $ ,
• para cada vértice $ v \ in l_ {k + 1} $ :
  • definir $ D [v]= + \ infty $
  • para cada borda $ (u, v) $ em $ e '$ :
    • update $ D [v] $ para $ \ min \ {d [v], d [u] + w (u, v) \} $
  • update $ D ^ * $ para $ \ min \ {d ^ *, d [v] \} $

Observe que isso requer tempo proporcional à $ | l_ {k + 1} | + | E '| $ , e é, portanto, assintoticamente otimal. Observe também que esta solução não precisa armazenar $ g $ .

Answer 2

Suponha que você tenha o comprimento dos caminhos mais curtos da raiz para todos os nós no nível $ l_i $ e ligue para este recipiente de matemática $ s \ in l_i \ to \ mathbb {z} $ .Agora suponha que as bordas da $ l_i $ para $ l_ {i + 1} $ são chamados $ E_I $ .Em seguida, o comprimento do caminho mais curto para um nó $ n $ em $ l_ {i + 1} $ é definido por $ \ min \ {w (x, n) + s (x) \ meados (x, n) \ em e_i \} $ .Manter os caminhos reais é uma extensão fácil.