1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Grafos em Java

Discussão em 'Programação' iniciada por lilcrazy, 23 de Abril de 2007. (Respostas: 10; Visualizações: 2487)

  1. lilcrazy

    lilcrazy Power Member

    Hey pessoal.

    Eu estou a implementar uma aplicação do género de um grafo em Java.
    A aplicação consiste na criação de companhias aéreas e respectivos percursos.

    Por exemplo existem os seguintes comandos:
    company:nomeDaCompanhia:velocidade -> cria um objecto do tipo companhia, atributos 2 parametros seguintes.

    insert:nomeDaCompanhia:origem:destino:distancia -> se ainda não existir este percurso (e notar que as distancias teem de ser diferentes para origens e destinos iguais) insere-o

    remove:nomeDaCompanhia:origem:destino -> se existir a companhia e a origem, remove o percurso

    etc.

    Para inserir percursos, eu tenho uma Hashtable que guarda objectos do tipo Companhia (key -> nome da companhia). Tenho outra Hashtable que guarda objectos do tipo Origem (key -> nome da cidade origem). Ao inserir percursos, vejo se ainda não existir essa origem na Hashtable, crio um objecto do tipo Destino e ligo a Origem ao destino. Ou seja a partir daqui são listas ligadas ordenadas alfabeticamente, ou seja, se inserirmos para a companhia TAP os seguintes percursos: Porto->Faro, Porto->Lisboa, Porto->Coimbra, ficaria na seguinte ordem

    PORTO -> COIMBRA -> FARO -> LISBOA

    Até aqui tudo bem...é de notar que podemos criar mais objectos do tipo Origem na Hashtable. Por exemplo, se inserirmos mais percursos...

    PORTO -> COIMBRA -> FARO -> LISBOA

    COIMBRA -> FARO -> LISBOA

    FARO -> LISBOA -> PARIS

    LISBOA -> FARO -> MADRID

    MADRID -> PARIS

    Agora estou a implementar um comando do tipo printByNumber, que percorre a partir duma origem várias cidades até encontrar a cidade destino passada como parametro (assim como a cidade origem). Se não encontrar o destino nunca, não imprime nada! Se encontrar, pode encontrá-lo de várias maneiras e podem ser necessários vários vôos. E aí tenho de no final ir comparando, se o numero de voos for maior que o percurso anterior, fica com o percurso anterior e imprime esse, pela ordem das cidades que passou. Se for menor, continua a procurar. Se não encontrar mais, imprime o último que encontrou, por ai em diante.

    Exemplo do comando -> printByNumber:origem:destino

    origem = porto, destino = paris

    possibilidades: Porto->Faro->Paris
    Porto->Lisboa->Madrid->Paris

    Ficando a primeira opção, uma vez, que se realizam menor número de voos do Porto para Paris.

    O problema está...como implemento isto? Percorrer todas as possibilidades? Já consegui este pedaço de código, mas qualquer coisa está mal, pois o percurso de Faro a Paris não é guardado :S

    Alguma ajuda?

    Ou alguma maneira mais fácil e menos confusa?

    Obrigado ;-)
     
  2. hYpe

    hYpe [email protected] Member

    Pesquisa pelo algoritmo de Ford Fulkerson, e implementa em Java.

    Ja fiz uma coisa parecida, mas em C++.
     
  3. lilcrazy

    lilcrazy Power Member

    Segundo percebi pela minha pesquisa, o ideal é criar uma pilha q va recebendo vertices certo?
     
  4. hYpe

    hYpe [email protected] Member

    Do que me lembro, sim.

    Nao tenho o programa comigo, mas vou pedir ao meu colega, e dps digo-te algm coisa!
     
  5. lilcrazy

    lilcrazy Power Member



    Raio, nunca consigo colocar o código aqui identado para que toda a gente perceba! lool

    O meu problema aqui é ir marcando os vértices, e depois ir verificando se o numVoos calculado no percurso anterior (isto caso tenha atingido o destino que se quer - passado como parametro) é maior ou menor. Se for menor entao guarda o menor, se for maior fica com o corrente (isto caso existam mais).

    Nesta parte estou empancado. Alguma ajuda?

    Obrigado pela disponibilidade ;-)
     
  6. HecKel

    HecKel The WORM

    em vez do [quote] TEXTO [/quote] usa o [code] CÓDIGO [/code]

    Sobre o teu problema, sinceramente ainda não o li bem :S

    abraços, HecKel
     
  7. Warrior

    Warrior Power Member

    Isto não me parece ser um problema de Max Flow mas sim de Shortest Path com edges unitários.
    Um Dijkstra ou um BFS (floodfill) resolvia o problema.
     
  8. MadOnion

    MadOnion Folding Member

    Um grafo tipo dijkstra era capaz de ser a melhor ideia, não sei é se seria bem implementável com as classes disponiveis na API, mas também ainda não investiguei a fundo. Só me lembro que precisei da noção de grafos num concurso de programação que tive.
     
  9. hYpe

    hYpe [email protected] Member

    Nao marques o vertice visitado, tendo em conta q e' um atributo do proprio vertice.

    Usa um vector chamado visitados, em que cada numero corresponde a um vertice.
     
  10. lilcrazy

    lilcrazy Power Member

    Alguma ajuda a implementar o algoritmo de Dijkstra?

    É que procurei tanto mas a ideia ficou, só que implementar o código para o meu programa tá dificil...

    Obrigado
     
  11. hYpe

    hYpe [email protected] Member

    No google encontrei isto:

    1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
    2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
    3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
    4. Let Si+1 = Si cup {ui+1}.
    5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.

    Tambem por la deve andar o codigo feito, mas acho q te faz bem faze-lo.
     

Partilhar esta Página