Grafos Buscador de Camino con Presupuesto Minimo

BuscadorCamino.java

public class BuscadorCamino {
	ListaGenerica<String> caminoConPresupuesto(Grafo<String> ciudades, String origen, String destino, int montoMaximo) {
		ListaGenerica<String> camino = new ListaEnlazadaGenerica<String>();
		ListaGenerica<String> temporal = new ListaEnlazadaGenerica<String>();
		boolean[] marca = new boolean[ciudades.listaDeVertices().tamanio() + 1];
		
		Vertice<String> vOrigen = buscar(ciudades, origen);
		
		if (vOrigen != null)
			caminoConPresupuesto(ciudades, destino, montoMaximo, camino, temporal, marca, vOrigen.getPosicion(), 0);
		
		return camino;
	}

	private void caminoConPresupuesto(Grafo<String> ciudades, String destino, int montoMaximo,
			ListaGenerica<String> camino, ListaGenerica<String> temporal, boolean[] marca, int i, int suma) {
		
		marca[i] = true;
		Vertice<String> v = ciudades.listaDeVertices().elemento(i);
		
		temporal.agregarFinal(v.dato());
		
		if (v.dato().equals(destino) && (suma < montoMaximo)) {
			clonar(camino, temporal);
		} else {
			ListaGenerica<Arista<String>> ady = ciudades.listaDeAdyacentes(v);
			ady.comenzar();
			while(!ady.fin()) {
				Arista<String> arista = ady.proximo();
				int j = arista.verticeDestino().getPosicion();
				if ((suma+=arista.peso()) < montoMaximo)
					if (!marca[j])
						caminoConPresupuesto(ciudades, destino, montoMaximo, camino, temporal, marca, j, suma+=arista.peso());
			}
			temporal.eliminarEn(temporal.tamanio());
		}
		
	}

	private void clonar(ListaGenerica<String> camino, ListaGenerica<String> temporal) {
		camino.comenzar();
		while(!camino.fin()) {
			camino.eliminarEn(camino.tamanio());
			camino.proximo();
		}
		
		temporal.comenzar();
		while(!temporal.fin()) {
			camino.agregarFinal(temporal.proximo());
		}
		
	}

	private Vertice<String> buscar(Grafo<String> ciudades, String lugar) {
		Vertice<String> v = null;
		ListaGenerica<Vertice<String>> vertices = ciudades.listaDeVertices();
		vertices.comenzar();
		while(!vertices.fin()) {
			v = vertices.proximo();
			if (v.dato().equals(lugar))
				return v;
		}
		return v;
	}
}

TestBuscadorDeCaminos.java

public class TestParcial1 {

	public static void main(String[] args) {
		VerticeImplListAdy<String> lincoln = new VerticeImplListAdy<String>("Lincoln");
		VerticeImplListAdy<String> chascomus = new VerticeImplListAdy<String>("Chascomus");
		VerticeImplListAdy<String> canuelas = new VerticeImplListAdy<String>("Cañuelas");
		VerticeImplListAdy<String> dolores = new VerticeImplListAdy<String>("Dolores");
		VerticeImplListAdy<String> veronica = new VerticeImplListAdy<String>("Veronica");
		VerticeImplListAdy<String> villaUrquiza = new VerticeImplListAdy<String>("Villa Urquiza");
		VerticeImplListAdy<String> ranchos = new VerticeImplListAdy<String>("Ranchos");
		VerticeImplListAdy<String> berisso = new VerticeImplListAdy<String>("Berisso");
		
		GrafoImplListAdy<String> ciudades = new GrafoImplListAdy<String>();
		
		ciudades.agregarVertice(lincoln);
		ciudades.agregarVertice(chascomus);
		ciudades.agregarVertice(canuelas);
		ciudades.agregarVertice(dolores);
		ciudades.agregarVertice(veronica);
		ciudades.agregarVertice(villaUrquiza);
		ciudades.agregarVertice(ranchos);
		ciudades.agregarVertice(berisso);
		
		ciudades.conectar(lincoln, chascomus, 70);
		ciudades.conectar(lincoln, canuelas, 50);
		ciudades.conectar(lincoln, dolores, 90);
		
		ciudades.conectar(chascomus, lincoln, 70);
		ciudades.conectar(chascomus, veronica, 80);
		ciudades.conectar(chascomus, villaUrquiza, 60);
		
		ciudades.conectar(canuelas, lincoln, 50);
		ciudades.conectar(canuelas, veronica, 85);
		ciudades.conectar(canuelas, ranchos, 90);
		
		ciudades.conectar(dolores, lincoln, 90);
		ciudades.conectar(dolores, villaUrquiza, 70);
		ciudades.conectar(dolores, ranchos, 70);
		
		ciudades.conectar(veronica, chascomus, 80);
		ciudades.conectar(veronica, canuelas, 85);
		ciudades.conectar(veronica, berisso, 60);
		
		ciudades.conectar(villaUrquiza, chascomus, 60);
		ciudades.conectar(villaUrquiza, dolores, 70);
		ciudades.conectar(villaUrquiza, berisso, 90);
		
		ciudades.conectar(ranchos, canuelas, 90);
		ciudades.conectar(ranchos, dolores, 70);
		ciudades.conectar(ranchos, berisso, 75);
		
		ciudades.conectar(berisso, veronica, 60);
		ciudades.conectar(berisso, villaUrquiza, 90);
		ciudades.conectar(berisso, ranchos, 75);
		
		BuscadorCamino buscadorCamino = new BuscadorCamino();
		System.out.println(buscadorCamino.caminoConPresupuesto(ciudades, "Lincoln", "Berisso", 200));
	}

}

Enunciado del ejercicio.
ejercicio_buscador_caminos.png