|
Título: Encontrar camino con DFS de origen a destino Publicado por: ruxcbe en 14 Noviembre 2014, 19:12 pm Hola, estoy intentado implementar este algoritmo para encontrar un camino de un vertice origen a uno destino. Guardando en un vector la id del vertice siguiente, la funcion debe retornar la capacidad del camino. (Es para el algoritmo de ford fulkerson).
Me he quedado trabado y tengo lo siguiente: Código: protected int trobacami(Graf G, int[] Path) { int vertex_inici = G.getInici(); int vertex_final = G.getFi(); Stack<Integer> s = new Stack(); int numV = G.getDimensioGraf(); inicialitzar(Path, numV); Path[vertex_final] = -2; int capacitat = Integer.MAX_VALUE; s.push(vertex_inici); while (!s.empty()) { int top = s.peek(); for (int aresta : G.arestesAdjacents(top)) { int segA = G.getIdFiAresta(aresta); if (G.getCapAresta(aresta) - G.getFluxeAresta(aresta) > 0 && Path[segA] == -1) { Path[segA] = top; int cap = G.getCapAresta(aresta) - G.getFluxeAresta(aresta); capacitat = min(cap, capacitat); if (segA != vertex_final) s.push(segA); else return capacitat; } } } return 0; } |