Olá pessoal, tudo bom?
Eu estou desenvolvendo um pequeno sistema de rotas em java onde a pessoa pode escolher uma cidade de origem e de destino e indicar o menor caminho.
Isto eu já consegui desenvolver utilizando busca heuristica, para o gerenciamento das rotas estou utilizando grafo mas eu tenho uma dúvida com relação a percorrimento de grafos:
Existe como eu descobrir todos os caminhos possíveis entre um determinado vértice a até um vértice b?
Isto pode ser útil, para que futuramente eu possa impor critérios na hora de percorrer o grafo como parametros como estrada, condições do tempo nesse trecho, etc… pois basicamente seria recuperar todos os caminhos possiveis e verificar qual caminho se aproximaria do criterio de busca escolhido.
Estou tentando bolar a lógica mas está complicado. Alguém que ja trabalhou com este tipo de problema poderia me ajudar com a lógica?
Acredito que vc possa embutir implicitamente suas condições usando o algoritmo de Dijkstra. Basta vc dar os pesos para os caminhos de acordo com as condições desejada. Agora se realmente vc kiser saber todos os caminhos possívels, acho que o algoritmo para encontrar a árvore geradosa (acho que é esse o nome) iria quebrar o seu galho. Dá uma pesquisada aí no Google que vc acha o algoritmo…
Olá amigo, muito obrigado pela orientação, já estou pesquisando…
mas vc pode me tirar uma duvida…a arvore geradora permite que eu especifique os vertices inicial e final para que mostre todas as ligações de arestas entre estes vértices?
Na verdade, uma árvore geradora de custo mínimo é o conjunto de n-1 arestas (n é o número de vértices) que conectam todos os vértices do grafo sem formar circuito.
Ela pode ser resolvida utilizando-se os algoritmos de kruskal ou prim. Existe uma estrutura chamada UNION-FIND que auxilia muito nisto, porém também é possível resolver na mão.
Já para encontrar o menor caminho de um para todos os demais vértices você utiliza o algoritmo de dijsktra.
Este algoritmo te permite dizer qual o vértice que você deseja que seja o inicial, e te diz os menores caminhos, desde o vértice que você escolheu como inicial até todos os demais.
Hummm…
Bom, o menor caminho eu já estou conseguindo encontrar utilizando busca heuristica, mas eu tb gostaria de implementar no meu programa uma opção que listasse todos os possiveis caminhos de um vertice A até um vértice B, porém pelo oque eu estou vendo é meio complicado neh…
tentei implementar na mão…pensei em usar recursividade…mas analisando o grafo a recursividade talvez não surta efeito pois dependendo do caminho, a função poderia entrar em um loop e não sair de lá…
Bom, o algoritmo de dijkstra te fornece dois vetores que contém os caminhos e as respectivas distâncias partindo de um vértice qualquer para todos os demais vértices.
Com esses dois vetores em mãos você consegue facilmente exibir os dados na tela.
É mais rápido você usar o algoritmo A* (busca heurística), do que Dijkstra. Use Dijkstra para pré-processar o grafo, se for o caso de um mapa muito estático, com poucos critérios (como mapa rodoviário).
A única coisa que você tem que mudar é o critério de avaliação do custo real, a partir do que seu usuário escolher. Então, recalcule a rota com o A* mesmo. O tempo é pequeno o suficiente para você não se preocupar. Ou você tem centenas de critérios?
