Encontrando k caminhos mais curtos com o algoritmo de Eppstein

16

Estou tentando descobrir como o Path Graph acordo com o algoritmo de Eppstein, neste artigo funciona e como posso reconstruir os caminhos mais curtos de para com a construção de pilha correspondente .P(G)kstH(G)

Tão longe:

out(v) contém todas as arestas que saem de um vértice em um gráfico de que não são parte de um caminho mais curto em . Eles são ordenados pelo heap pelo "desperdício de tempo" chamado ao usar essa borda em vez da que está nos caminhos mais curtos. Aplicando o Dijkstra, encontro os caminhos mais curtos para todos os vértices de .vGGδ(e)t

Eu posso calcular isso tomando o comprimento da aresta + (o valor do vértice da cabeça (onde a aresta direcionada está apontando para) - o valor do vértice da cauda (onde a aresta direcionada está iniciando) .Se for , não está no caminho mais curto, se for , está no caminho mais curto.>0=0

Agora que construir um 2-Min-Heap por heapifying o conjunto de arestas o u t ( v ) de acordo com a sua δ ( e ) para qualquer v V , onde a raiz o u t r o o t ( v ) tem apenas um filho (= subárvore).Hout(v)out(v)δ(e)vVoutroot(v)

A fim de construir I inserção o u t r o o t ( v ) em H T ( n e x t T ( v ) ) com início no vértice do terminal t . Sempre que um vértice é tocado de alguma forma durante a inserção, ele é marcado com um .HT(v)outroot(v)HT(nextT(v))t

Agora, podemos construir , inserindo o resto de H o u t ( w ) em H T ( v ) . Cada vértice em H L ( v ) contém ou duas crianças de H T ( v ) e 1 a partir de H o u t ( w ) ou 0 a partir do primeiro e 2 a partir do segundo e é um 3-montão.HG(v)Hout(w)HT(v)HG(v)2HT(v)1Hout(w)02

Com I pode construir um DAG chamado D ( L ) que contém um vértice para cada * vértice -marked de H T ( v ) e para cada vértice não raiz de H o u t ( v ) .HG(v)D(G)HT(v)Hout(v)

As raízes de em D ( G ) são chamadas h ( v ) e estão conectadas aos vértices aos quais pertencem de acordo com o u t ( v ) por um "mapeamento".HG(v)D(G)h(v)out(v)

Por enquanto, tudo bem.

O artigo diz que eu posso construir inserindo uma raiz r = r ( s ) e conectando-a a h ( s ) por uma borda inicial com δ ( h ( s ) ) . Os vértices de D ( G ) são os mesmos em P ( G ), mas não são ponderados. As arestas têm comprimentos. Então, para cada aresta direcionada ( u , v ) D ( G )P(G)r=r(s)h(s)δ(h(s))D(G)P(G)(u,v)D(G)as arestas correspondentes em são criadas e ponderadas por δ ( v ) - δ ( u ) . Eles são chamados de Heap Edges. Então, para cada vértice v P ( G ) , que representa uma aresta que não está no caminho mais curto que conecta um par de vértices u e w , "arestas transversais" são criadas de v a h ( w ) em P ( G ) com um comprimento δ ( h ( wP(G)δ(v)δ(u)vP(G)uwvh(w)P(G) . Todo vértice em P ( G ) possui apenas um grau de saída de 4 máx.δ(h(w))P(G)4

caminhos 's a partir de r é suposto ser uma correspondência comprimento de um-para-um entre o s - t -paths em L .P(G)rstG

No final, uma nova pilha ordenada 4-Heap é compilada. Cada vértice corresponde a um caminho em P ( G ) enraizado em r . O pai de qualquer vértice tem uma borda a menos. O peso de um vértice é o comprimento do caminho correspondente.H(G)P(G)r

Para encontrar os caminhos mais curtos, uso o BFS em P ( G ) e "traduzo" o resultado da pesquisa em caminhos usando H ( G ) .kP(G)H(G)

Infelizmente, não entendo como posso "ler" e depois "traduzi-lo" através de H ( G ) para receber os k caminhos mais curtos.P(G)H(G)k

Laura
fonte
6
Você verificou as várias implementações em ics.uci.edu/~eppstein/pubs/p-kpath.html ?
Radu GRIGore

Respostas:

25

Já faz bastante tempo desde que escrevi isso, que agora minha interpretação do que está lá provavelmente não está muito mais informada do que qualquer outro leitor. Mesmo assim:

Acredito que a descrição que você está procurando é o último parágrafo da prova do Lema 5. Basicamente, algumas das arestas em P (G) (as "arestas transversais") correspondem às desvias em G (ou seja, arestas que divergem da árvore do caminho mais curto). O caminho em G é formado seguindo a árvore do caminho mais curto até o vértice inicial do primeiro percurso, seguindo a própria borda do percurso, seguindo a árvore do caminho mais curto novamente para o vértice inicial do próximo percurso etc.

David Eppstein
fonte
11
Como observação lateral, esse algoritmo parece ter sido recentemente superado. Os detalhes podem ser encontrados aqui
Carlos Linares López
David, eu realmente preciso de uma implementação do seu algoritmo, melhor em Java. Você pode me apontar onde eu posso encontrar um?
Tina J
11
As implementações que eu conheço estão vinculadas na parte inferior de ics.uci.edu/~eppstein/pubs/p-kpath.html - mas não verifiquei as fora do site recentemente, portanto, pode haver alguns deadlinks.
David Eppstein
Obrigado. Mais importante, porém, você tem um pseudocódigo completo do seu algoritmo disponível em algum lugar?
Tina J
@DavidEppstein Algo parecido com o de Dijkstra na Wikipedia: en.wikipedia.org/wiki/K_shortest_path_routing
Tina J
4

O pseudocódigo para o algoritmo de Eppstein (e a versão lenta dos autores) é apresentado em: VM Jiménez, A. Marzal, Uma versão lenta do algoritmo de caminhos mais curtos de Eppstein, em: 2º Workshop Internacional de Algoritmos Experimentais e Eficientes (WEA '03), in: Notas de aula em Ciência da Computação, vol. 2647, Springer, 2003, pp. 179-190. https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf

tmn
fonte