Dijkstra

DijkistraTest.java

import static org.junit.Assert.*;

import org.junit.Test;

public class DijkistraTest {

	@Test
	public void testDistancia() {
		GrafoComListaDeAdjacencias grafo = 
				new GrafoComListaDeAdjacencias("JP", "MA", "AL", "GU", "CG",
						"QU", "AC", "PA", "MO", "PI", "SO", "CJ");
		
		Vertice jp = grafo.getVertice("JP");
		Vertice ma = grafo.getVertice("MA");
		Vertice al = grafo.getVertice("AL");
		Vertice gu = grafo.getVertice("GU");
		Vertice cg = grafo.getVertice("CG");
		Vertice qu = grafo.getVertice("QU");
		Vertice ac = grafo.getVertice("AC");
		Vertice pa = grafo.getVertice("PA");
		Vertice mo = grafo.getVertice("MO");
		Vertice pi = grafo.getVertice("PI");
		Vertice so = grafo.getVertice("SO");
		Vertice cj = grafo.getVertice("CJ");

		grafo.addAresta(jp, ma, 40);
		grafo.addAresta(gu, ma, 40);
		grafo.addAresta(jp, gu, 60);
		grafo.addAresta(pi, gu, 100);
		grafo.addAresta(jp, cg, 120);
		grafo.addAresta(jp, al, 40);
		grafo.addAresta(cg, gu, 100);
		grafo.addAresta(cg, pi, 160);
		grafo.addAresta(cg, pa, 180);
		grafo.addAresta(cg, mo, 200);
		grafo.addAresta(cg, qu, 20);
		grafo.addAresta(pa, so, 200);
		grafo.addAresta(qu, ac, 40);
		grafo.addAresta(so, cj, 100);

//		assertEquals(120, grafo.menorDistancia(cg, jp));
//		assertEquals(160, grafo.menorDistancia(jp, pi));
		assertEquals(600, grafo.menorDistancia(jp, cj));
	}
	
}

GrafoComListaDeAdjacencias.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class GrafoComListaDeAdjacencias implements Grafo {

	private List<Vertice> vertices = new ArrayList<>();
	private List<VerticeInterno> verticesInternos = new ArrayList<>();

	public GrafoComListaDeAdjacencias(String... nomesVertices) {
		for (String nomeVertice : nomesVertices) {
			this.addVertice(nomeVertice);
		}
	}
	public void buscaPorProfundidadeTotal() {
		boolean[] visitados = new boolean[vertices.size()];

		VerticeInterno naoVisitado = encontrarNaoVisitado(visitados);
		
		do {
			buscaP(naoVisitado, visitados);
		} while ( (naoVisitado = encontrarNaoVisitado(visitados) ) != null);
	}
	
	protected VerticeInterno encontrarNaoVisitado(boolean[] visitados) {
		for (int i = 0; i < visitados.length; i++) {
			boolean visitado = visitados[i];
			if (!visitado) {
				return verticesInternos.get(i);
			}
		}
		return null;
	}
	
	public void buscaPorProfundidade() {
		buscaPorProfundidade(vertices.get(0));
	}
	

	public void buscaPorProfundidade(Vertice vertice) {
		boolean[] visitados = new boolean[vertices.size()];
		buscaP(getVerticeInterno(vertice), visitados);
	}

	private void buscaP(VerticeInterno vertice, boolean[] visitados) {
		int posicao = verticesInternos.indexOf(vertice);
		
		if (visitados[posicao]) {
			return;
			
		} else {
			visitados[posicao] = true;
			System.out.println(vertice.getVertice().getNome());
			for (Aresta aresta : vertice.getArestas()) {
				
				buscaP(getVerticeInterno(aresta.getDestino()), visitados);		
			}
		}	
	}

	@Override
	public Vertice addVertice(String nome) {
		Vertice vertice = new Vertice();
		vertice.setNome(nome);
		vertices.add(vertice);
		
		VerticeInterno verticeInterno = new VerticeInterno();
		verticeInterno.setVertice(vertice);
		verticesInternos.add(verticeInterno);
		
		return vertice;
	}
	
	public Vertice getVertice(String nome) {
		for (Vertice vertice: vertices) {
			if (vertice.getNome().equals(nome)) {
				return vertice;
			}
		}
		
		return null;
	}
	
	private VerticeInterno getVerticeInterno(Vertice v) {
		for (VerticeInterno verticeInterno : verticesInternos) {
			if (verticeInterno.getVertice().equals(v)) {
				return verticeInterno;
			}
		}
		
		throw new RuntimeException("Vertice interno não encontrado");
	}

	@Override
	public void addAresta(Vertice v1, Vertice v2, int distancia) {
		Aresta ida = new Aresta();
		ida.setOrigem(v1);
		ida.setDestino(v2);
		ida.setDistancia(distancia);
		VerticeInterno verticeInternoV1 = getVerticeInterno(v1);
		verticeInternoV1.getArestas().add(ida);

		Aresta volta = new Aresta();
		volta.setOrigem(v2);
		volta.setDestino(v1);
		volta.setDistancia(distancia);
		VerticeInterno verticeInternoV2 = getVerticeInterno(v2);
		verticeInternoV2.getArestas().add(volta);

	}

	@Override
	public List<Vertice> getVertices() {
		return vertices;
	}

	@Override
	public boolean conecta(Vertice v1, Vertice v2) {
		VerticeInterno verticeInternoV1 = getVerticeInterno(v1);
		
		for (Aresta aresta : verticeInternoV1.getArestas()) {
			if (aresta.getDestino().equals(v2)) {
				return true;
			}
		}
		
		return false;
	}
	
	public void buscaPorLargura(Vertice inicial) {
		boolean[] visitados = new boolean[vertices.size()];
		Queue<VerticeInterno> aVisitar = new LinkedList<>();
		
		VerticeInterno interno = getVerticeInterno(inicial);
		int posicaoInicial = verticesInternos.indexOf(interno);
		visitados[posicaoInicial] = true;
		
		aVisitar.offer(interno);
		
		while (!aVisitar.isEmpty()) {
			interno = aVisitar.remove();

			System.out.println(interno.getVertice().getNome());
			visitarArestas(visitados, aVisitar, interno);
		}
	}
	
	protected void visitarArestas(boolean[] visitados, Queue<VerticeInterno> aVisitar, VerticeInterno interno) {
		for (Aresta aresta : interno.getArestas()) {
			Vertice destino = aresta.getDestino();
			tentarEnfileirar(visitados, aVisitar, destino);
		}
	}
	
	protected void tentarEnfileirar(boolean[] visitados, Queue<VerticeInterno> aVisitar, Vertice destino) {
		VerticeInterno verticeInterno = getVerticeInterno(destino);
		
		if (!visitados[verticesInternos.indexOf(verticeInterno)]) {
			visitados[verticesInternos.indexOf(verticeInterno)] = true;
			aVisitar.offer(verticeInterno);
		}
	}
	public int menorDistancia(Vertice origem, Vertice destino) {
		int quantidadeVertices = vertices.size();

		int[] distancias = inicializaDistancias(origem, quantidadeVertices);
		boolean[] verticesAbertos = inicializaVerticesAbertos(quantidadeVertices);
		Vertice[] predecessores = new Vertice[quantidadeVertices];

		while (existeVerticeAberto(verticesAbertos)) {
			VerticeInterno menorEstimativa = menorEstimativa(verticesAbertos, distancias);
			fecharVertice(verticesAbertos, menorEstimativa);
			
			for (Aresta aresta : menorEstimativa.getArestas()) {
				relaxa(aresta, distancias, verticesAbertos, predecessores);
			}
		}
		
		imprimir(predecessores, destino);
		
		return distancias[vertices.indexOf(destino)];
	}
	
	private void imprimir(Vertice[] predecessores, Vertice destino) {
		Vertice atual = destino;
		
		while (atual != null) {
			System.out.println(atual.getNome());
			atual = predecessores[vertices.indexOf(atual)];
		}
	}
	protected int[] inicializaDistancias(Vertice origem, int quantidadeVertices) {
		int[] distancias = new int[quantidadeVertices];
		Arrays.fill(distancias, Integer.MAX_VALUE);
		int posicaoOrigem = vertices.indexOf(origem);
		distancias[posicaoOrigem] = 0;
		return distancias;
	}
	
	protected boolean[] inicializaVerticesAbertos(int quantidadeVertices) {
		boolean[] verticesAbertos = new boolean[quantidadeVertices];
		Arrays.fill(verticesAbertos, true);
		return verticesAbertos;
	}
	
	protected void fecharVertice(boolean[] verticesAbertos, VerticeInterno vertice) {
		verticesAbertos[verticesInternos.indexOf(vertice)] = false;
	}
	
	private boolean existeVerticeAberto(boolean[] verticesAbertos) {
		for (int i = 0; i < verticesAbertos.length; i++) {
			boolean verticeAberto = verticesAbertos[i];
			if (verticeAberto) return true;
		}
		return false;
	}
	
	private VerticeInterno menorEstimativa(boolean[] verticesAbertos, int[] distancias) {
		int menorEstimativa = Integer.MAX_VALUE;
		int posicao = -1;
		for (int i = 0; i < distancias.length; i++) {
			if (verticesAbertos[i] && distancias[i] < menorEstimativa) {
				menorEstimativa = distancias[i];
				posicao = i;
			}
		}
		return verticesInternos.get(posicao);
	}
	
	private void relaxa(Aresta aresta, int[] distancias, boolean[] verticesAbertos, Vertice[] predecessores) {
		int posicaoOrigem = vertices.indexOf(aresta.getOrigem());
		int posicaoDestino = vertices.indexOf(aresta.getDestino());
		
		if (verticesAbertos[posicaoDestino]) {
			int distanciaAnteriorDestino = distancias[posicaoDestino];
			int possivelNovaDistanciaDestino = distancias[posicaoOrigem] + aresta.getDistancia();
			
			if (possivelNovaDistanciaDestino < distanciaAnteriorDestino) {
				distancias[posicaoDestino] = possivelNovaDistanciaDestino;
				predecessores[posicaoDestino] = vertices.get(posicaoOrigem);
			}
		}
	}
}

class VerticeInterno {

	private Vertice vertice;
	private List<Aresta> arestas = new ArrayList<>();

	public Vertice getVertice() {
		return vertice;
	}

	public void setVertice(Vertice vertice) {
		this.vertice = vertice;
	}

	public List<Aresta> getArestas() {
		return arestas;
	}

}