Algoritmo Menor Caminho

Semana passada me pediram ajuda com a implementação de um algoritmo de menor caminho. O pessoal precisava calcular a menor rota entre dois vértices de um grafo, levando em consideração o custo do caminho. Para quem ainda não percebeu, esse é o algoritmo desenvolvido por Djikstra.

Suponha que você tem um conjunto de pontos interligados, como lugares ligados por ruas e estradas, e precisa calcular o menor caminho entre dois pontos. O grafo abaixo mostra um exemplo de um situação como essa.

Os pontos podem ser cidades e os números nas setas podem ser vistos como a distância ou o custo entre duas cidades.

O algoritmo de Djikstra consistem em calcular o menor caminho, a partir da origem, a cada ponto caminhado no grafo até o destino. O código abaixo mostra como sua implementação é simples.

Note que o algoritmo verifica se o destino já foi alcançado e se o próximo vértice do grafo já foi percorrido. Isso impede que os caminhos sejam analisados indefinidamente.

public class Djikstra {

 /**
  * Calcula a menor rota entre a origem e o destino.
  * 
  * @param caminhoPercorrido
  *            O caminho percorrido até aqui
  * @return O custo total do caminho percorrido.
  */
 public static Double calcularMenorCaminho(Vertice origem,
   Vertice destino, List<Vertice> caminhoPercorrido) {

  Double menor = Double.POSITIVE_INFINITY;
  Double custo = 0.0;

  // Adiciona a origem ao caminho percorrido
  caminhoPercorrido.add(origem);

  // Se a origem for igual ao destino, encerra a busca
  if (origem.equals(destino)) {
   return custo;
  }

  // Armazena o caminho percorrido até aqui
  List<Vertice> caminhoAnterior = new ArrayList<Vertice>(
    caminhoPercorrido);
  List<Vertice> caminho = null;

  // Verifica cada caminho possível
  for (Entry<Vertice, Double> proximoVertice : origem
    .getProximosVertices().entrySet()) {

   // Inicia o novo caminho
   caminho = new ArrayList<Vertice>(caminhoAnterior);

   // Define o custo do caminho como infinito, pois ainda não se sabe
   // se ele leva ao destino desejado
   custo = Double.POSITIVE_INFINITY;

   // Percorre o caminho a partir do próximo nodo, desde que este não
   // tenha sido percorrido
   if (!caminho.contains(proximoVertice.getKey())) {
    custo = proximoVertice.getValue()
      + calcularMenorCaminho(proximoVertice.getKey(),
        destino, caminho);
   }

   // Verifica se o caminho percorrido é melhor que o anterior
   if (custo < menor) {
    menor = custo;

    // Atualiza o melhor caminho
    caminhoPercorrido.clear();
    caminhoPercorrido.addAll(caminho);
   }
  }

  return menor;
 }
}

A classe abaixo é utilizada para realizar a representação de um grafo. Organizando os pontos e os destinos acessíveis a partir de um ponto.

/**
 * Define os atributos de cada ponto no grafo e os possíveis
 * caminhos de saída de cada ponto
 */
class Vertice {

 private String nome;
 private Map<Vertice, Double> proximosVertices
    = new HashMap<Vertice, Double>();

 public Vertice(String nome) {
  super();
  this.nome = nome;
 }

 @Override
 public boolean equals(Object obj) {
  if (obj != null && obj instanceof Vertice) {
   Vertice objVertice = (Vertice) obj;

   return (this.nome == null && objVertice.nome == null)
     || this.nome.equals(objVertice.nome);
  }

  return false;
 }

 public String getNome() {
  return nome;
 }

 public Map<Vertice, Double> getProximosVertices() {
  return proximosVertices;
 }

 @Override
 public int hashCode() {
  return nome != null ? nome.hashCode() : 0;
 }

 @Override
 public String toString() {
  return nome;
 }
}

O trecho abaixo mostra construção do grafo e como o método é utilizado para o nosso exemplo.

public static void main(String[] args) {
 Vertice a = new Vertice("A");
 Vertice b = new Vertice("B");
 Vertice c = new Vertice("C");
 Vertice d = new Vertice("D");
 Vertice e = new Vertice("E");
 Vertice f = new Vertice("F");
 Vertice g = new Vertice("G");

 a.getProximosVertices().put(b, 1.0);
 a.getProximosVertices().put(c, 2.0);
 a.getProximosVertices().put(d, 1.0);

 b.getProximosVertices().put(e, 4.0);

 c.getProximosVertices().put(e, 3.0);

 d.getProximosVertices().put(f, 2.0);

 e.getProximosVertices().put(g, 7.0);
 e.getProximosVertices().put(f, 2.0);

 f.getProximosVertices().put(g, 3.0);

 b.getProximosVertices().put(c, 4.0);
 c.getProximosVertices().put(d, 1.0);
 c.getProximosVertices().put(b, 1.0);
 d.getProximosVertices().put(a, 1.0);
 d.getProximosVertices().put(e, 1.0);
 f.getProximosVertices().put(d, 2.0);

 List<Vertice> menorCaminho = new ArrayList<Vertice>();
 Double menorCusto = calcularMenorCaminho(a, g, menorCaminho);

 System.out.println(menorCusto);
 for (Vertice vertice : menorCaminho) {
  System.out.print("=> " + vertice.getNome() + " ");
 }
}