Encontrar camino con DFS de origen a destino

Iniciado por ruxcbe, 14 Noviembre 2014, 19:12 PM

0 Miembros y 1 Visitante están viendo este tema.

ruxcbe

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:

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