Dijsktra

public class Link {

	private Node origem;
	private Node destino;
	public int peso;

//pegar a distancia
	public Link(Node origem, Node destino, int peso) {

		this.origem  = origem;
		this.destino = destino;
		this.peso    = peso;
	}

	public Node getOrigem() {
		return this.origem;
	}

	public Node getDestino() {
		return this.destino;
	}

	public boolean contains(Node node) {
		return (origem.equals(node) || destino.equals(node));
	}

	public Node getPair(Node node) {
		Node pair = null;
		if (origem.equals(node)) {
			pair = destino;
		} else if (destino.equals(node)) {
			pair = destino;
		}
		return pair;
	}

	public String toString() {
		return "(" + origem.toString() + "," + destino.toString() + "," + peso + ")";
	}

}

public class Node {

	private Object info;
	public Node No;
	public Link[] adjacencias;
	public double distanciaMinima = Double.POSITIVE_INFINITY;
	protected LinkedList<Link> links;

	public Node(Object info) {
		this.info = info;
	}

	public void setInfo(Object info) {
		this.info = info;
	}

	public Object getInfo() {
		return info;
	}

	public String toString() {
		return info.toString();
	}

	public static void main(String[] args) {

	//	String origem, destino;

		// Scanner entrada = new Scanner(System.in);

		 //System.out.println("Informe a Origem: ");

		// origem = entrada.nextLine();

		// System.out.println("Informe o Destino: ");

		// destino = entrada.nextLine();

		// Criando nós

		//
		Node Recife 		= new Node("Recife");
		Node JoaoPessoa 	= new Node("Joao Pessoa");
		Node CampinaGrande 	= new Node("Campina Grande");
		Node Ipojuca 		= new Node("Ipojuca");
		Node Escada 		= new Node("Escada");
		Node Gravata 		= new Node("Gravata");
		Node Vitoria 		= new Node("Vitoria");
		Node Gloria 		= new Node("Gloria");
		Node Bezerros 		= new Node("Bezerros");
		Node Caruaru 		= new Node("Caruaru");
		Node Agrestina	 	= new Node("Agrestina");
		Node SaoCaetano 	= new Node("São Caetano");
		Node Toritama 		= new Node("Toritama");
		Node SantaCruz 		= new Node("Santa Cruz");
		Node Taquaritinga 	= new Node("Taquaritinga");
		Node Surubim 		= new Node("Surubim");
		Node Limoeiro 		= new Node("Limoeiro");
		Node Carpina 		= new Node("Carpina");

		// Raiz
		Grafo mapa = new Grafo(Recife);

		// adocionando no mapa os nós, caso precise criar mais
		mapa.add(Recife, Ipojuca, 40);
		mapa.add(Recife, JoaoPessoa, 100);
		mapa.add(Recife, Vitoria, 40);
		mapa.add(Recife, Carpina, 40);
		mapa.add(JoaoPessoa, CampinaGrande, 100);
		mapa.add(Ipojuca, Escada, 20);
		mapa.add(Vitoria, Carpina, 40);
		mapa.add(Vitoria, Gravata, 40);
		mapa.add(Vitoria, Escada, 30);
		mapa.add(Vitoria, Gloria, 20);
		mapa.add(Gravata, Bezerros, 20);
		mapa.add(Bezerros, Caruaru, 20);
		mapa.add(Caruaru, SaoCaetano, 20);
		mapa.add(Caruaru, Agrestina, 40);
		mapa.add(Caruaru, Toritama, 40);
		mapa.add(Toritama, SantaCruz, 20);
		mapa.add(Toritama, Surubim, 40);
		mapa.add(SantaCruz, Taquaritinga, 20);
		mapa.add(Taquaritinga, Surubim, 40);
		mapa.add(Surubim, CampinaGrande, 80);
		mapa.add(Surubim, Limoeiro, 40);
		mapa.add(Carpina, Limoeiro, 40);
		mapa.add(Limoeiro, Surubim, 40);
		mapa.add(Limoeiro, Gloria, 20);
		
		//mapa.MelhorCaminho(origem, destino);
		
		mapa.MelhorCaminho(Recife, Surubim);

	}	
}

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Grafo {
	public static Double Distancia = Double.MAX_VALUE;

	private Node raiz;
	LinkedList<Node> Visitas = new LinkedList<Node>();

	protected LinkedList<Link> links;

	public Grafo(Node root) {
		this.raiz = root;
		this.links = new LinkedList<Link>();
	}

	public void add(Node node, Node node2, int peso) {
		this.links.add(new Link(node, node2, peso));

	}

	public String toString() {
		return "raiz = " + this.raiz.toString() + ". Links: " + this.links;
	}

	public LinkedList<Node> getLinks(Node node) {
		LinkedList<Node> nos = new LinkedList<Node>();
		for (int i = 0; i < this.links.size(); i++) {
			Link link = this.links.get(i);
			if (link.contains(node)) {
				nos.add(link.getPair(node));
			}
		}
		return nos;
	}

	static String Encontrado = "";

	private void CaminhoNo(Node Origem, Node Destino, LinkedList<Node> Lista,
			double soma) {

		double SomaDistancia = soma;

		LinkedList<Node> ListaVisitas = new LinkedList<Node>();

		// Adiciona todos os Nodes do retorno.
		ListaVisitas.addAll(Lista);

		// Verifica se o Node Já existe na lista, caso exista vai para o proximo
		// Node
		if (!ListaVisitas.contains(Origem)) {

			// Caso o Node Não exista na Lista ele é adicionado

			ListaVisitas.add(Origem);

			// Cria um For each percorrendo todos os links existentes
			for (Link DistanciaCaminhos : links) {

				// Se Lista Visitas tiver mais de um iten faz a comparação com
				// links da posicao de "From" com
				// ListaVistas.get(ListaVisitas.size()-2) que sempre sera uma
				// posicao de destino inicial do link
				// e ListaVistas.get(ListaVisitas.size()-1) com a posicao To de
				// Link
				if (ListaVisitas.size() > 1) {

					if (DistanciaCaminhos.getOrigem().equals(
							ListaVisitas.get(ListaVisitas.size() - 2))
							&& DistanciaCaminhos.getDestino().equals(
									ListaVisitas.get(ListaVisitas.size() - 1))) {

						// Se a conexão entre os links existir é somado o peso
						// entre eles.
						SomaDistancia += DistanciaCaminhos.peso;

						// Caso o caminho de Links Venha ser igual ao destino eh
						// impresso na tela
						// a rota feita até o destino e impresso a sua soma de
						// até o ponto de destino.
						if (DistanciaCaminhos.getDestino().equals(Destino)
								&& SomaDistancia < Distancia) {

							Distancia = SomaDistancia;
							Encontrado = "" + ListaVisitas.toString()
									+ "  Distancia " + Distancia + "\n\n";
						}
					}

				}

			}

			LinkedList<Node> ListaNode = new LinkedList<Node>();

			ListaNode.addAll(getLinks(Origem));
			//
			for (int i = 0; i < ListaNode.size(); i++) {

				if ((!ListaNode.get(i).equals(Origem))) {

					// ListaEncontrado.addAll(ListaDestino);

					CaminhoNo(ListaNode.get(i), Destino, ListaVisitas,
							SomaDistancia);

				}
			}
		}

	}

	void MelhorCaminho(Node from, Node to) {

		LinkedList<Node> visitas = new LinkedList<Node>();

		CaminhoNo(from, to, visitas, 0);
		System.out.println("Menor Caminho Encontrado: " + Encontrado);

	}

}