Aresta.java

public class Aresta {

	private Vertice origem;
	private Vertice destino;
	private int distancia;

	public Vertice getOrigem() {
		return origem;
	}

	public void setOrigem(Vertice origem) {
		this.origem = origem;
	}

	public Vertice getDestino() {
		return destino;
	}

	public void setDestino(Vertice destino) {
		this.destino = destino;
	}

	public int getDistancia() {
		return distancia;
	}

	public void setDistancia(int distancia) {
		this.distancia = distancia;
	}

}

Grafo.java

import java.util.List;

public interface Grafo {

	Vertice getVertice(String nome);
	
	Vertice addVertice(String nome);

	void addAresta(Vertice v1, Vertice v2, int distancia);

	List<Vertice> getVertices();

	int getDistanciaDireta(Vertice v1, Vertice v2);

}

GrafoComListaDeAdjacencias.java

import java.util.ArrayList;
import java.util.List;

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);
		}
	}
	
	@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 int getDistanciaDireta(Vertice v1, Vertice v2) {
		VerticeInterno verticeInternoV1 = getVerticeInterno(v1);
		
		for (Aresta aresta : verticeInternoV1.getArestas()) {
			if (aresta.getDestino().equals(v2)) {
				return aresta.getDistancia();
			}
		}
		
		return -1;
	}

}

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;
	}

}

GrafoComMatrizDeAdjacencia.java

import java.util.Arrays;
import java.util.List;

public class GrafoComMatrizDeAdjacencia implements Grafo {

	private int[][] matriz;
	private Vertice[] vertices;
	private int contatorVertices = 0;
	
	public GrafoComMatrizDeAdjacencia(String... nomesVertices) {
		int quantidadeDeVertices = nomesVertices.length;
		matriz = new int[quantidadeDeVertices][quantidadeDeVertices];
		
		vertices = new Vertice[quantidadeDeVertices];
		for (String nomeVertice : nomesVertices) {
			this.addVertice(nomeVertice);
		}
	}

	@Override
	public Vertice addVertice(String nome) {
		Vertice vertice = new Vertice();
		vertice.setNome(nome);
		vertices[contatorVertices++] = vertice;

		return vertice;
	}

	@Override
	public Vertice getVertice(String nome) {
		for (Vertice vertice: vertices) {
			if (vertice.getNome().equals(nome)) {
				return vertice;
			}
		}
		
		return null;
	}
	
	private int getPosicao(Vertice v) {
		for (int i = 0; i < vertices.length; i++) {
			Vertice vertice = vertices[i];
			
			if (vertice.getNome().equals(v.getNome())) {
				return i;
			}
		}
		
		throw new RuntimeException("Vertice nao encontrado");
	}
	
	@Override
	public void addAresta(Vertice v1, Vertice v2, int distancia) {
		int origem = getPosicao(v1);
		int destino = getPosicao(v2);
		
		matriz[origem][destino] = distancia;
	}

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

	@Override
	public int getDistanciaDireta(Vertice v1, Vertice v2) {
		int origem = getPosicao(v1);
		int destino = getPosicao(v2);
		
		int distancia = matriz[origem][destino];
		
		return (distancia == 0) ? -1 : distancia;
	}

}

GrafoTest.java

import static org.junit.Assert.*;

import java.util.List;

import org.junit.Test;

public class GrafoTest {

	@Test
	public void test() {
		Grafo grafo = 
				new GrafoComMatrizDeAdjacencia("Mamanguape", "Rio Tinto", 
						"Marcacao", "Baía da traição", "Sapé", "Capim", 
						"Santa Rita", "Cuité de Mamanguape", "Jacaraú",
						"Itapororoca");
		
		Vertice mamanguape = grafo.getVertice("Mamanguape");
		Vertice rioTinto = grafo.getVertice("Rio Tinto");
		Vertice marcacao = grafo.getVertice("Marcacao");
		Vertice baiaDaTraicao = grafo.getVertice("Baía da traição");
		Vertice sape = grafo.getVertice("Sapé");
		Vertice capim = grafo.getVertice("Capim");
		Vertice santaRita = grafo.getVertice("Santa Rita");
		Vertice cuiteDeMamanguape = grafo.getVertice("Cuité de Mamanguape");
		Vertice jacarau = grafo.getVertice("Jacaraú");
		Vertice itapororoca = grafo.getVertice("Itapororoca");

		grafo.addAresta(mamanguape, rioTinto, 8);
		grafo.addAresta(rioTinto, marcacao, 9);
		grafo.addAresta(marcacao, baiaDaTraicao, 14);
		grafo.addAresta(mamanguape, jacarau, 36);
		grafo.addAresta(mamanguape, itapororoca, 14);
		grafo.addAresta(itapororoca, cuiteDeMamanguape, 10);
		grafo.addAresta(cuiteDeMamanguape, capim, 11);
		grafo.addAresta(capim, sape, 24);
		grafo.addAresta(capim, mamanguape, 12);
		grafo.addAresta(mamanguape, santaRita, 45);
		grafo.addAresta(sape, santaRita, 39);
		
		List<Vertice> vertices = grafo.getVertices();
		
		assertTrue(vertices.contains(mamanguape));
		assertTrue(vertices.contains(rioTinto));
		assertTrue(vertices.contains(marcacao));
		assertTrue(vertices.contains(baiaDaTraicao));
		assertTrue(vertices.contains(sape));
		assertTrue(vertices.contains(capim));
		assertTrue(vertices.contains(santaRita));
		assertTrue(vertices.contains(cuiteDeMamanguape));
		assertTrue(vertices.contains(jacarau));
		assertTrue(vertices.contains(itapororoca));
		assertEquals(10, vertices.size());
		
		assertEquals(8, grafo.getDistanciaDireta(mamanguape, rioTinto));
		assertEquals(9, grafo.getDistanciaDireta(rioTinto, marcacao));
		assertEquals(14, grafo.getDistanciaDireta(marcacao, baiaDaTraicao));
		assertEquals(36, grafo.getDistanciaDireta(mamanguape, jacarau));
		assertEquals(14, grafo.getDistanciaDireta(mamanguape, itapororoca));
		assertEquals(10, grafo.getDistanciaDireta(itapororoca, cuiteDeMamanguape));
		assertEquals(11, grafo.getDistanciaDireta(cuiteDeMamanguape, capim));
		assertEquals(24, grafo.getDistanciaDireta(capim, sape));
		assertEquals(12, grafo.getDistanciaDireta(capim, mamanguape));
		assertEquals(45, grafo.getDistanciaDireta(mamanguape, santaRita));
		assertEquals(39, grafo.getDistanciaDireta(sape, santaRita));

		assertEquals(-1, grafo.getDistanciaDireta(mamanguape, baiaDaTraicao));
		assertEquals(-1, grafo.getDistanciaDireta(mamanguape, sape));
		assertEquals(-1, grafo.getDistanciaDireta(mamanguape, marcacao));
		assertEquals(-1, grafo.getDistanciaDireta(rioTinto, itapororoca));
		assertEquals(-1, grafo.getDistanciaDireta(sape, baiaDaTraicao));

	}

	
	
	
	
	
	
	
}

Vertice.java

public class Vertice {

	private String nome;

	public String getNome() {
		return nome;
	}

	public void setNome(String nome) {
		this.nome = nome;
	}

}