O código utiliza a biblioteca JUNG2 (atualmente na versão beta), e mais duas classes próprias (Vertice e Aresta), bem simples. A biblioteca é utilizada apenas para receber um Graph, do tipo Vertice, Aresta.
O objetivo é mostrar a implementação do algoritmo, pois o JUNG2 já possui a implementação, basta usar a classe DijkstraShortestPath.
Para usar a classe, intancie fazendo Dijkstra dijkstra = new Dijkstra(). Em seguida, use o método dijkstra.getMenorCaminho(grafo, verticeOrigem, verticeDestino);
- Crie um pacote chamado "modelo" e coloque as classes a seguir:
Classe Vertice
package modelo;
public class Vertice {
private String nome;
private boolean flagOrigemDestino = false;
public Vertice(){
this.nome = "v";
}
public Vertice(String nome){
this.nome = nome;
}
public String getNome() {
return nome;
}
public void setNome(String nome) {
this.nome = nome;
}
public boolean isFlagOrigemDestino() {
return flagOrigemDestino;
}
public void setFlagOrigemDestino(boolean flagOrigemDestino) {
this.flagOrigemDestino = flagOrigemDestino;
}
@Override
public String toString() {
return nome;
}
@Override
public boolean equals(Object obj) {
return ((Vertice)obj).getNome().equalsIgnoreCase(this.nome);
}
}
Classe Aresta
package modelo;
public class Aresta {
private int peso = 0;
private boolean flagCaminho = false;
public Aresta(int peso){
this.peso = peso;
}
public int getPeso() {
return peso;
}
public void setPeso(int peso) {
this.peso = peso;
}
public boolean isFlagCaminho() {
return flagCaminho;
}
public void setFlagCaminho(boolean flagCaminho) {
this.flagCaminho = flagCaminho;
}
@Override
public String toString() {
return String.valueOf(peso);
}
}
- Crie um pacote chamado "dijkstra" e coloque a classe a seguir:
Classe Dijkstra
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import modelo.Aresta;
import modelo.Vertice;
import edu.uci.ics.jung.graph.Graph;
public class Dijkstra {
private final Comparator comparatorDistancia = new Comparator() {
public int compare(Vertice v1, Vertice v2) {
int distV1 = distancias.get(v1);
int distV2 = distancias.get(v2);
if (distV1 > distV2)
return +1;
else if (distV1 <>
return -1;
else
return 0;
}
};
private HashSet nosFechados = new HashSet(); // nós resolvidos
private PriorityQueue nosAbertos = new PriorityQueue(10,comparatorDistancia);// nós nao calculados
private HashMap distancias = new HashMap();// distancia, vertice
private HashMap antecessores = new HashMap();// vertice, vertice antecessor
public List getMenorCaminho(Graph g,
Vertice origem, Vertice destino) {
// reseta estruturas
nosFechados.clear();
nosAbertos.clear();
distancias.clear();
antecessores.clear();
distancias.put(origem, 0);
nosAbertos.add(origem);
for(Vertice v : g.getVertices())
distancias.put(v, Integer.MAX_VALUE);
// enquanto houver vertices na nuvem
while (!nosAbertos.isEmpty()) {
Vertice u = nosAbertos.poll(); // pega vertice de menor distancia
if (nosFechados.contains(u)) // se vertice ja foi calculado, continuar
continue;
if (u == destino) // chegamos ao destino, parar
break;
nosFechados.add(u); // vertice calculado
// atualizar distancias e caminho
for (Vertice v : g.getNeighbors(u)) {
if (nosFechados.contains(v))
continue;
Aresta arestaUV = g.findEdge(u, v); // pega aresta entre u e v
int dist = distancias.get(u) + arestaUV.getPeso();
if (dist <>
// atualiza distancia de v
distancias.put(v, dist);
// setPai
antecessores.put(v, u);
// adiciona a nuvem
nosAbertos.add(v);
}
}
}
// compõe menor caminho
LinkedList menorCaminho = new LinkedList();
Aresta a;
Vertice u;
Vertice v = destino;
while( (u = antecessores.get(v)) != null){
a = g.findEdge(v, u);
v = u;
menorCaminho.add(a);
}
Collections.reverse(menorCaminho);
return menorCaminho;
}
}
