Podemos encontrar k caminhos mais curtos entre todos os pares mais rapidamente do que resolver o problema aos pares repetidamente?

9

Eu quero produzir caminho mais curto ( k seria menor que 10) entre todos os pares em um gráfico. O gráfico é (na verdade um mapa do metrô):kk

  • ponderado positivamente
  • sem direção
  • escasso
  • com cerca de 100 nós

Meu plano atual é aplicar o caminho mais curtok a cada par; Agora estou procurando uma alternativa mais eficiente (possivelmente com programação dinâmica).

algorithms graphs optimization shortest-path Franklin Yu
fonte
3
Honestamente, para 100 vértices, parece improvável que você precise de algo mais eficiente do que resolver cada um dos 45.000 problemas em pares.
David Richerby

Respostas:

6

k

O todos os paresk

Esta parece ser uma área de pesquisa bastante jovem. Um artigo recente de Agarwal e Ramachandran pode ser encontrado no ArXiv [1]. A seção de trabalho anterior também fornecerá algumas dicas sobre o histórico do problema.

O paresk

Aqui, de fato, é a melhor opção para aplicar repetidamente o algoritmo Eppsteins [2]. A observação geral de que uma aplicação repetida de um algoritmo para a versão de fonte única do problema é a abordagem mais rápida já foi feita em 1977 por EL Lawler [3]; Eppstein fornece o algoritmo mais rápido até hoje para esse subproblema.

Referências

k

[2] Eppstein, D. Encontrando os k caminhos mais curtos. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, EL Comente sobre a computação dos k caminhos mais curtos de um gráfico. Communications of the ACM, 20 (8): 603–605, 1977.

FiB
fonte
Obrigado. Como estou trabalhando com o mapa do metrô, preciso que eles sejam um caminho simples (não faz sentido para o meu software guiar as pessoas a ir e voltar), então acho que iria apenas com o algoritmo de Yan .
Franklin Yu
Interessante e bastante surpreendente que aparentemente 10.000 casos de um problema não possam ser resolvidos mais rapidamente do que apenas resolver 10.000 casos únicos, um após o outro.
precisa saber é o seguinte
a idéia de caminhos com loops incluídos nos "caminhos mais curtos" parece contra-intuitiva e incomum, porque aparentemente existe um "caminho" equivalente com o loop removido, e também se pergunta se eles podem ser eficientemente construídos a partir dos caminhos simples, etc ...
vzn 11/08/16