Eu tenho um grande conjunto de redes lineares e gostaria de encontrar as duas extremidades de cada rede que estão mais distantes uma da outra ao longo da rede (na imagem abaixo, seria D a K). A solução de força bruta para esse problema é calcular o caminho mais curto ao longo da rede para cada par de origem, mas eu tenho centenas de redes com milhares de fins, portanto, calcular cada caminho possível é bastante pesado.
Existe uma maneira ideal de calcular isso sem usar a força bruta? Posso excluir alguns pontos com base em regras inteligentes?
EDIT: Adicionei uma ilustração do caminho mais longo mencionado por @Alex Tereshenkov para esclarecer minha pergunta. O caminho preto é o resultado do algoritmo de caminho mais longo (caminho mais longo sem repetir nenhum vértice). No meu caso, imagine que você entra na rede a partir de qualquer uma das letras e precisa dirigir para outra letra o mais rápido possível. Quais as duas letras mais difíceis de aderir?
Respostas:
Acho que você pode estar procurando pelo diâmetro do gráfico da sua rede. Há algumas perguntas sobre stackexchange que mencionam este tópico, por exemplo:
A maioria dos algoritmos sugere calcular primeiro os "caminhos mais curtos de todos os pares" e selecionar o mais longo, mas eu encontrei um post de Koushik Narayanan no blog que sugere uma abordagem alternativa que pode ser mais ideal (não verifiquei), o que itera sobre cada vértice e encontra seu par mais distante:
fonte
De acordo com a página da Wikipedia Problema com o caminho mais longo , esse problema
Se você trabalha com (ou pode representar seu gráfico como DAG ), o
networkx
pacote Python permitirá que você o calcule. Procure a funçãodag_longest_path
.A menos que esteja faltando alguma coisa, você precisará calcular o comprimento entre os nós do gráfico e classificá-los que, infelizmente, funcionarão apenas em tempo linear , ou seja, não há algoritmo eficiente para isso.
fonte