Boa tarde,
Gostaria de saber se alguém conhece algum método para busca por maior caminho em um grafo… Por busca pelo menor caminho é bem fácil encontrar definições e implementações, mas por uma busca por maior caminho não encontrei nada até agora… Já tentei usar o mesmo princípio de algoritmos usados em menor caminho, mas não se aplica… Então se alguém puder me ajudar com algum link ou indicação d livro, agradeço. 
Grato desde já
David
Não poderia simplesmente buscar todas as possibilidades e ir guardando a que for maior?
O maior caminho tem comprimento infinito se você não limitar o percurso - basta fazer um caminho entrar em loop.
Portanto, você provavelmente precisa de uma limitação adicional, do tipo “você não pode percorrer o mesmo vértice duas ou mais vezes”, ou outra, do tipo “percorrer todos os vértices do grafo que forem alcançáveis (reachable)”.
Oi, david_ware.
Para obter o maior caminho mantenhas em mente que tu nunca podes passar duas vezes pela mesma aresta e duas vezes pelo mesmo vértice.
Tu poderias usar de apoio o caminho Euleriano para encontrar o caminho longo passando pela areasta apenas uma vez.
Espero que ajude.
É verdade… tinha esquecido de falar sobre a limitação. Neste caso em questão, há um vértice de saída e um ou mais aceitáveis como destino. A limitação é no número de “passos”, ou seja, o número de vezes que se passa de um vértice para outro. Portanto, não necessariamente irá percorrer todos os vértices do grafo. Nesse Também tinha pensado em percorrer todas as possibilidades, mas dependendo do número de vértices, arestas e passos, irá aumentar muito o tempo de execução.
Olá, tguerra.
Achei bem interessante a idéia de caminho euleriano, mas nesse caso não há garantia de que o grafo tenha grau par. Mas mesmo assim, obrigado, não conhecia essa teoria.
Oi, david_ware.
Então, eu não sei se você já havia visto, mas talvez esse link ajude: Longest Path Problem. E também dá uma olhada nesse blog, explica muito bem: Dijkstra e o caminho máximo.