Jump to content
zegeremias

Dijkstra

Recommended Posts

zegeremias

Pretendo descobrir o caminho mais curto entre 2 nos de 1 grafo (pesado) e o caminho mais curto que passe por todos os nos.

O melhor é o algoritmo de dijkstra? e há alguma forma de um implementar sendo o meu grafo implementado com uma matriz de adjacencias?

Share this post


Link to post
Share on other sites
zegeremias

ok, entao como poderia ser o algoritmo visto ter as minhas classes assim:


public class Graph<T> implements GraphADT<T> {
       protected final int DEFAULT_CAPACITY = 10;
       protected int numVertices; // number of vertices in the graph
       protected boolean[][] adjMatrix; // adjacency matrix
       protected T[] vertices; // values of vertices
       //tem ainda os metodos necessarios como addEdge e addvertex...
}
public class Aresta<T> {

       private T verticeInicio;
       private T verticeFim;
       private double peso;
       //(...)
}
public class Network<T> extends Graph<T> implements NetworkADT<T> {
       protected Aresta[] arestas;
       /**
        * Creates an empty graph.
        */
       public Network() {
               super();
               numVertices = 0;
               this.adjMatrix = new boolean[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
               this.vertices = (T[]) (new Object[DEFAULT_CAPACITY]);
               this.arestas = (Aresta[]) (new Object[0]);
       }
       //tambem com os metodos necessarios como addEdge e addvertex...
}

isso é so um excerto das classes que penso serem principais... se alguem conseguir ajudar agradecia

Edited by Baderous
geshi

Share this post


Link to post
Share on other sites
HappyHippyHippo

afinal queres que te criem o código ou tens dúvidas no que o algoritmo faz/se processa ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
zegeremias

eu procuro o algoritmo na net e n parece que encaixa nas minhas classes, por isso era para ver se alguem tinha/sabia o codigo correto

Share this post


Link to post
Share on other sites
HappyHippyHippo

se o que pretendes é o código, então vou deixar de seguir este tópico.

se o problema é perceber o algoritmo (algo que parece ser o caso por não saberes aplicar-lo ao código que tens) então terás de apresentar o que realmente não percebes no algoritmo.


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Rui Carlos

Basicamente, precisas que a tua estrutura de dados seja capaz de te devolver os vizinhos de um nó (é simples, basta percorrer uma linha/coluna da matriz de adjacência), e o peso das arestas (precisas de saber onde está a informação da aresta).

O código da Wikipédia deve servir (pelo menos para a parte do caminho mais curto entre dois nós).

Podes começar por converter o código da Wikipédia (ou outro), e depois indicas o que é que não conseguiste fazer.

Share this post


Link to post
Share on other sites
zegeremias

o shortestPathWeight da class network calcula o custo minimo entre 2 nos?

o minSpanningTree faz o mesmo?

e qual devo usar para verificar o que custo menos e que passe por todos?

Share this post


Link to post
Share on other sites
Rui Carlos
minSpanningTree deve ser para calcular a árvore de extensão mínima do grafo, que pode ser vista como uma solução para a segunda parte do problema, se bem que o resultado obtido não é propriamente um caminho. Caso a solução tenha mesmo que ser um caminho, então diria que o problema que tens em mãos é o do caixeiro viajante (que é um problema NP-hard).

Share this post


Link to post
Share on other sites
zegeremias

surgiu-me outro problema, depois de colocar o shortestestPathWeight a funcionar.

Eu tenho vertices ligados por arestas que pretende que sejam bidireccionais, e outras que pretendo que nao sejam bidireccionais, mas ele ta a assumir que sao sempre... como poderei resolver isto atraves de mais algum addEgde ou alterando o shortestestPathWeight

Share this post


Link to post
Share on other sites
Rui Carlos

Define o grafo como não direccionado, e quando tiveres uma ligação nos dois sentidos, adicionas duas ligações em cada sentido.

Penso que estás a usar uma matriz de adjacência, pelo que agora a tua matriz deixará de ser simétrica. Se tiveres apenas ligação do nó N para o nó M (e não o contrário), isso significa que adjMatrix[N][M] será true, e adjMatrix[M][N] será false (também podes fazer ao contrário).

Share this post


Link to post
Share on other sites
zegeremias

ja esta tudo a funcionar, o erro estava nos algoritmos de caminho mais curto, obrigado.

Share this post


Link to post
Share on other sites
FilhoDoSol

Pretendo descobrir o caminho mais curto entre 2 nos de 1 grafo (pesado)

Os pesos dos arcos podem ser negativos? Se sim o Dijkstra não funciona, e tens de usar o Bellman–Ford.
e o caminho mais curto que passe por todos os nos.
Para este tens de usar o Prim ou o Kruskal.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.