Shortest path

import java.util.Vector;

public class Graph {

	private Vector<Vertex> vertices; // contém os vértices do grafo

	// construtor do grafo
	public Graph() {
		vertices = new Vector<Vertex>();
	}

	/*
	 * valida se existem os vértices que são passados quando se controiem os
	 * arcos
	 */

	public boolean validate(String id1) {
		for (int i = 0; i < vertices.size(); ++i)
			if ((vertices.elementAt(i).getId().equalsIgnoreCase(id1))) {

				return true;
			}
		return false;
	}

	/*
	 * adiciona um arco ao vertice do grafo com id = id1, um arco que termina no
	 * vértice com id=id2 e peso w
	 */
	public boolean addEdge(String id1, String id2, int w) {
		if (!validate(id1))
			return false;
		if (!validate(id2))
			return false;

		Vertex v1 = this.get(id1);
		Vertex v2 = this.get(id2);
		if (v1.addEdge(v2, w))
			return true;
		return false;

	}

	/*
	 * retorna o vértice do grafo com id igual ao recebido como parametro ou
	 * null caso não exista
	 */

	public Vertex get(String id) {
		for (int i = 0; i < vertices.size(); ++i) {
			if (vertices.elementAt(i).getId().equals(id)) {
				return vertices.get(i);
			}
		}
		return null;
	}

	/*
	 * retorna o vértice do gráfico com index igual ao passado por parametro ou
	 * null caso não exista
	 */

	public Vertex get(int v) {
		for (int i = 0; i < vertices.size(); ++i) {
			if (vertices.elementAt(i).getIndex() == v) {
				return vertices.get(i);
			}
		}
		return null;
	}

	// retorna os ids dos vértices
	public String idsVertices() {
		String id = "";
		String aux = "";
		for (int i = 0; i < vertices.size(); ++i) {
			aux = vertices.elementAt(i).getId();
			id += "[" + " " + aux + " ]";
		}
		return id;
	}

	// retorna o número de vertices
	public int getSize() {
		return vertices.size();
	}

	/*
	 * remove um arco se ele existir neste grafo. Retorna true ou false
	 * consoante a remoção se concretize ou não.
	 */

	public boolean removeEdge(WeightedEdge e) {
		Vertex init = e.getInit();
		Vertex rem = null;

		for (int i = 0; i < vertices.size(); ++i) {
			if (vertices.elementAt(i).equals(init)) {
				rem = vertices.elementAt(i);
			}
		}
		rem.removeEdge(e);
		return false;
	}

	/*
	 * método que retorna um objecto String com o seguinte formato:
	 * 
	 * [(vo1, vd1, w1), (vo2,vd2,w2), . . ., (von,vdn,wn)]
	 * 
	 * Em que cada triplo (voi,vdi, wi), i Î{1, ...,n} representa um objecto do
	 * tipo WeightedEdge.
	 */

	public String toString() {
		String aux = "";
		String st = "";
		for (int i = 0; i < vertices.size(); ++i) {
			Vertex v = vertices.elementAt(i);
			aux = v.vertexToEdgeToString();
			st += aux;
		}
		return "[" + st + "]";
	}

	/*
	 * retorna o vértice do grafo com id igual ao recebido como parametro, caso
	 * não exista um vertice com este id adiciona ao grafo um novo vértice com
	 * este id e index igual à posição em que foi adicionado
	 */

	public Vertex vertex(String id) {
		for (int i = 0; i < vertices.size(); ++i) {
			if (vertices.elementAt(i).getId().equals(id)) {
				return vertices.get(i);
			}
		}
		Vertex ver = new Vertex(id, vertices.size());
		vertices.add(ver);
		return ver;
	}

}

public class WeightedEdge {

	private int weight; // peso do arco

	private Vertex init, end; // vértice de inicio e fim do arco

	// cria um arco com inicio em vo, fim em vd e peso p
	public WeightedEdge(Vertex vo, Vertex vd, int p) {
		this.init = vo;
		this.end = vd;
		this.weight = p;
	}

	// retorna true se o objecto ref arco igual,false caso contrário
	// 2 arcos são iguais se ligarem os mesmos vértices
	public boolean equals(Object o) {
		if (o instanceof WeightedEdge) {
			WeightedEdge we = (WeightedEdge) o;
			if (((this.init == we.init) && (this.end == we.end))
					|| ((this.end == we.init) && (this.init == we.end)))
				return true;
		}
		return false;
	}

	// retorna o vértice de destino do arco
	public Vertex getEnd() {
		return (this.end);
	}

	// retorna o vértice de origem do arco
	public Vertex getInit() {
		return (this.init);
	}

	// retorna o peso do arco
	public int getWeight() {
		return weight;
	}

	// exibe o arco e os seus parâmetros
	public String toString() {
		return "(" + this.init + "," + this.end + "," + this.weight + ")";
	}
}

import java.util.*;

public class Vertex {

	private String id; // id do vértice

	private int index;

	private LinkedList<WeightedEdge> edges; // contêm a lista de arcos q têm origem neste vértice

	public Vertex(String id, int index) {
		edges = new LinkedList<WeightedEdge>();
		this.id = id; // identificador do vértice
		this.index = index; // indice onde o vértice se encontra no grafo
	}

	//Adiciona um novo arco a edges, com origem neste 
	// vértice, fim e peso passados como parâmetros 

	public boolean addEdge(Vertex d, int p) {

		WeightedEdge we = new WeightedEdge(this, d, p);
		return (edges.add(we)); // como o método add é boolean vai retornar true se for adicionado

	}

	//retorna true se o objecto referencia um vértice, caso contrário é falso
	public boolean equals(Object o) {
		if (o instanceof Vertex) {
			Vertex v = (Vertex) o;
			if (this.id == v.id)
				return true;
		}
		return false;
	}

	//Percorre a lista de arcos e retorna um iterador para os vértices 
	public VertexIterator getEdgesIterator() {
		VertexIterator vI = new VertexIterator();
		return vI;
	}

	// retorna o id do vértice
	public String getId() {
		return id;
	}

	//retorna o index do vértice 
	public int getIndex() {
		return index;
	}

	//remove um arco da lista de arcos deste mesmo vértice
	public boolean removeEdge(WeightedEdge a) {
		Iterator it = edges.listIterator();
		while (it.hasNext()) {
			if (a.equals(it.next())) {
				it.remove();
				return true;
			}
		}
		return false;
	}

	//retorna o id do vértice
	public String toString() {
		return getId();
	}

	//Inner Class 

	//Classe VertexIterator, percorre os vértices dos arcos da lista 

	public class VertexIterator implements Iterator {
		Iterator it = edges.listIterator();

		//testa se há seguinte
		public boolean hasNext() {
			return (it.hasNext());
		}

		//retorna o próximo elemento
		public Vertex next() {
			WeightedEdge we = (WeightedEdge) it.next();
			return we.getEnd();
		}

		//remove um arco
		public void remove() {
			it.remove();
		}

	}

	public String vertexToEdgeToString() {
		Iterator it = edges.listIterator();
		String s = "";
		String s1 = "";
		while (it.hasNext()) {
			WeightedEdge we = (WeightedEdge) it.next();
			s1 += we.toString();
		}
		return s += s1;

	}

}

import java.util.*;

public class caminhos {
	Graph grafo = null;

	Vertex init, end;

	String i, e;

	public caminhos(Graph grafo) {
		this.grafo = grafo;
	}

	public static void main(String[] args) {
		int nEdge;
		Graph g = new Graph();
		String init;
		String end;
		int peso;

		Scanner sc = new Scanner(System.in);

		System.out
				.println("Introduza o número de ligações entre dois cruzamentos consecutivos das pistas :");
		nEdge = sc.nextInt();

		for (int i = 0; i < nEdge; i++) {
			System.out.println("Introduza a ligação " + i
					+ " entre 2 cruzamentos consecutivos das pistas :");
			init = sc.next();
			end = sc.next();
			peso = sc.nextInt();

			g.vertex(init);
			g.vertex(end);
			g.addEdge(init, end, peso);

		}
		System.out.println(g.toString());

	}

}