Existe um algoritmo ideal para encontrar o caminho mais curto e mais longo de uma rede?

13

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?

Como encontrar com eficiência o caminho vermelho?

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? insira a descrição da imagem aqui

radouxju
fonte
pintura maluca skillz!
Adam

Respostas:

6

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:

Podemos calcular o caminho de um vértice V1, de modo que seja o caminho mais curto entre V1 e um do vértice e seja maior que o caminho mais curto entre qualquer outro vértice. Veja este post para um algoritmo. Em seguida, podemos percorrer todos os vértices e encontrar o caminho mais longo com todos os vértices como raiz. Depois de termos a lista de todos os caminhos mais curtos mais longos, podemos encontrar o que possui o valor máximo e retorná-lo.

mkadunc
fonte
obrigado, o diâmetro do gráfico era exatamente o que eu estava procurando e a heurística do pseudo-diamter funciona no meu caso. Acabei de aprender novas palavras lá!
Radouxju
7

De acordo com a página da Wikipedia Problema com o caminho mais longo , esse problema

... é NP-difícil, o que significa que não pode ser resolvido em tempo polinomial para gráficos arbitrários, a menos que P = NP. Resultados mais fortes da dureza também são conhecidos, mostrando que é difícil aproximar. No entanto, possui uma solução de tempo linear para gráficos acíclicos direcionados, que possui aplicações importantes para encontrar o caminho crítico nos problemas de agendamento.

Se você trabalha com (ou pode representar seu gráfico como DAG ), o networkxpacote Python permitirá que você o calcule. Procure a função dag_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.

Alex Tereshenkov
fonte
Obrigado pela resposta, já + 1 por causa da informação. No entanto, estou procurando o mais longo caminho mais curto em uma rede (no meu exemplo, nenhum desvio em direção a B ou H). Portanto, sua solução não é exatamente o que estou procurando, mesmo que indique que a "força bruta" é provavelmente a única solução.
precisa saber é o seguinte
@radouxju, ah eu vejo. Bem, vamos ver se o gene notará isso, ele tem muita experiência com gráficos, talvez ele tenha algumas idéias brilhantes.
Alex Tereshenkov