Shortest path

Programação Java
#1

oi galera…
Sou nova aki no grupo e no java também e já tou com umas duvidazitas, se a galera me puder ajudar :lol: :lol: :lol:

eu tenho um trabalho que estou fazendo no qual eu tenho que calcular a menor distância entre 2 vertices num grafo, o problema é que eu sou bem iniciante nisso do java e não estou conseguindo fazer. Me deram uma dica para usar um método recursivo mas não estou a ver quais o parametros que vou receber nem o algoritmo não.
eu tenho um grafo que tem as vertices num vector e cada vertice tem uma linkedList com todas as arestas que estão partindo desse mesmo vértice.
Eu já consegui criar isso tudo mas agora tenho 3 métodos para criar que não tou conseguindo,

  1. O número de caminhos entre cada par de cruzamentos
  2. A menor distância entre cada par de cruzamentos;
  3. O caminho mais curto entre cada par de cruzamentos.

Peço desculpa se isto fôr uma pergunta demasiado básica para vocês, mas para mim é mesmo muito complicado
:shock:

#2

[quote=TelmaSofia]oi galera…
Sou nova aki no grupo e no java também e já tou com umas duvidazitas, se a galera me puder ajudar :lol: :lol: :lol:

eu tenho um trabalho que estou fazendo no qual eu tenho que calcular a menor distância entre 2 vertices num grafo, o problema é que eu sou bem iniciante nisso do java e não estou conseguindo fazer. Me deram uma dica para usar um método recursivo mas não estou a ver quais o parametros que vou receber nem o algoritmo não.
eu tenho um grafo que tem as vertices num vector e cada vertice tem uma linkedList com todas as arestas que estão partindo desse mesmo vértice.
Eu já consegui criar isso tudo mas agora tenho 3 métodos para criar que não tou conseguindo,

  1. O número de caminhos entre cada par de cruzamentos
  2. A menor distância entre cada par de cruzamentos;
  3. O caminho mais curto entre cada par de cruzamentos.

Peço desculpa se isto fôr uma pergunta demasiado básica para vocês, mas para mim é mesmo muito complicado
:shock:

[/quote]

Vc deu uma procurada nas mensagens anteriores ?Tem uma galera fazendo esse trabalho de grafos por ae…mas vai ae umas dicas:

:idea: http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra
:idea: http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html
:arrow: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
:arrow: http://www.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html

Um Abraço !

#3

Parece que esse Dijkstra Algorithm é o que eu preciso… vou tentar implementar no meu trabalho :lol: :lol:

#4

Tem o A*, até onde eu sei muito usado em jogos e em alguma situações específicas, segue um ótimo link para programação para jogos.

http://theory.stanford.edu/~amitp/GameProgramming/

#5