Tenho de implementar este algoritmo mas estou com alguns problemas
O algoritmo funciona bem no caso de ser um grafo assim.
Cria-se o objecto algoritmo, e faz-se
No caso de ser algo mais elaborado, tipo isto
1 2 803
2 1 803
2 3 12
3 4 158
2 4 10000
4 3 158
Em que a primeira coluna e segunda coluna são cidades, e a terceira é a distancia entre cidades.
No caso de se querer ir da cidade 1 para a cidade 4, o caminho correcto seria: 1 - 2 - 3 - 4
O problema é que lança uma excepção: NullPointerException neste código (que é originada no próprio algoritmo (procurar onde está comentado/*AQUI*/))
Provavelmente é o o algoritmo que está mal implementado. Se alguém conseguir dar uma ajudinha agradecia 
Código:
//Função que determina o menor caminho possível entre duas cidades - a flag servirá para indicar se o caminho a calcular é o melhor em distância (true) ou tempo(false)
public ArrayList<Cidade> menorCaminho(Cidade origem, Cidade destino, boolean flag)
{
if (origem.getN() == destino.getN())
throw new IllegalArgumentException("Cidade de origem igual 'a cidade de destino");
Cidade menor = null, actual = null;
//O menor caminho começa com a origem
cidades_minimo.add(origem);
actual = origem;
//inicializa todas as cidades
Iterator<Cidade> it = cidades.iterator();
while (it.hasNext())
{
Cidade cidade = (Cidade) it.next();
if(flag == true) {
if (cidade.getN() == actual.getN()) {
actual.setDistancia(0);
cidade = actual;
}
else
cidade.setDistancia(infinito); //a distância a cada cidade é infinita por defeito
}
// else
// cidade.setTempo(infinito);
cidade.setAnterior(null);
}
actual = origem; //inicialmente a cidade actual é a cidade origem
//procura as cidades vizinhas à origem
ArrayList<Cidade> adjacentes = actual.getCidadesVizinhas();
//caso não existam cidades vizinhas, não existe nenhum caminho possível
try
{
if (adjacentes == null)
throw new IllegalArgumentException("Nao existe nenhum caminho possivel");
else
{
//caso contrário, as vizinhas são definidas como as cidades anteriores da origem
it = adjacentes.iterator();
while (it.hasNext())
{
Cidade cidade = (Cidade)it.next();
cidade.setAnterior(origem);
}
//Aqui começa verdadeiramente o algoritmo
//Enquanto a cidade actual não for a cidade de destino
while (actual.getN() != destino.getN())
{
ArrayList<Cidade> adjacentes_aux = new ArrayList<Cidade>();
//a menor alternativa, caso inicial
menor = null;
for (int i = 0; i < cidades.size(); i++)
{
if (existe((cidades.get(i)).getN()) == false) //se a cidade ainda não tiver sido visitada
{
if (menor == null) //para o caso inicial, menor é a primeira cidade da lista
menor = cidades.get(i);
Cidade c = cidades.get(i); //c é a cidade em análise
if (actual.getCidadesVizinhas() == null)
throw new IllegalArgumentException("Nao existe nenhum caminho possivel");
if (actual.getCusto(c) == 0) {
++i;
continue;
}
//se a distância à cidade anterior + o custo da cidade em análise for menor que a distância à anterior da cidade em análise
//e se a cidade já tiver sido inicializada
/*AQUI*/ if (actual.getPeso(flag) + actual.getCusto(c) < actual.getPeso(flag))
{
if (actual.getCusto(c) < infinito) {
//muda a distância da cidade actual para a distância "optimizada"
if(flag == true)
c.setDistancia(actual.getPeso(flag) + actual.getCusto(c));
else
c.setTempo(actual.getPeso(flag) + actual.getCusto(c));
}
if (actual.getCusto(c) < infinito)
c.setAnterior(actual);
}
if (c.getPeso(flag) < menor.getPeso(flag)) //se a distância da cidade actual for menor do que até agora foi considerada menor, menor passa a ser c
menor = c;
}
}
actual = menor; //a cidade em análise no próximo ciclo passa a ser a menor encontrada no ciclo for anterior
cidades_minimo.add(actual); //e é adicionada à lista do menor caminho
}
//ArrayList para guardar o menor caminho
ArrayList<Cidade> minimo = new ArrayList<Cidade>(cidades_minimo.size());
//Define o último nó do menor caminho como o actual
actual = cidades_minimo.get(cidades_minimo.size()-1);
//Insere na pilha todos os elementos do menor caminho para ordenar
while (actual != null)
{
minimo.add(0,actual);
actual = actual.getAnterior();
}
cidades_minimo = minimo;
return minimo;
}
}
catch (IllegalArgumentException e)
{
System.err.println(e.getMessage());
return null;
}
}
Código:
ArrayList<Cidade> Cidades = new ArrayList<Cidade>();
Cidade SMI = new Cidade("S.Mamede Infesta");
Cidades.add(SMI);
Cidade Custoias = new Cidade("Custóias");
Cidades.add(Custoias);
new Estrada(SMI,Custoias,3);
Cidade Balio = new Cidade("Leça do Balio");
Cidades.add(Balio);
new Estrada (Custoias,Balio,2);
Cidade Hora = new Cidade("Senhora da Hora");
Cidades.add(Hora);
new Estrada(Custoias,Hora, 3);
new Estrada(Hora, Balio,4);
origem = SMI;
destino = Balio;
Código:
alg.caminhoMaisCurto(Origem, Destino, flag)1 2 803
2 1 803
2 3 12
3 4 158
2 4 10000
4 3 158
Em que a primeira coluna e segunda coluna são cidades, e a terceira é a distancia entre cidades.
No caso de se querer ir da cidade 1 para a cidade 4, o caminho correcto seria: 1 - 2 - 3 - 4
O problema é que lança uma excepção: NullPointerException neste código (que é originada no próprio algoritmo (procurar onde está comentado/*AQUI*/))
Código:
// Função que devolve o peso da estrada (em que o peso pode ser a distância ou tempo) que une a cidade à cidade de destino da mesma
public int getCusto(Cidade destino)
{
for (int i = 0; i < estradas.size(); i++)
{
Estrada estrada = estradas.get(i);
//se a origem for esta cidade e o destino da estrada for a cidade dada como argumento ou vice versa
/*AQUI*/ if ((estrada.getOrigem().getN() == this.nCidade && estrada.getDestino().getN() == destino.getN())
||
(estrada.getOrigem().getN() == destino.getN() && estrada.getDestino().getN() == this.nCidade))
{
return estrada.getPeso();
}
//else
//return Integer.MAX_VALUE;
}
return Integer.MAX_VALUE; //se não se verificar a condição anterior, devolve infinito, que é o valor por defeito considerado no algoritmo de Dijkstra
}
Última edição:
