elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Encontrar camino con DFS de origen a destino
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Encontrar camino con DFS de origen a destino  (Leído 1,614 veces)
ruxcbe

Desconectado Desconectado

Mensajes: 2


Ver Perfil
Encontrar camino con DFS de origen a destino
« 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;
    }


« Última modificación: 14 Noviembre 2014, 22:57 pm por ruxcbe » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Problema con destino
Desarrollo Web
agredesniak 1 2,380 Último mensaje 3 Julio 2010, 17:53 pm
por agredesniak
Encontrar origen de foto en Facebook
Dudas Generales
t36 2 5,566 Último mensaje 5 Agosto 2012, 12:05 pm
por Puntoinfinito
Caminos posibles de un nodo origen a un nodo destino.
Ejercicios
Anquilat 0 2,705 Último mensaje 15 Noviembre 2013, 13:12 pm
por Anquilat
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines