Número de caminos entre nodos de un grafo

Con el fin de ayudar a los compañeros que han acudido a mi blog solicitando ayuda para la práctica he invertido unas cuantas horas en resolver el problema añadido de este año “Obtener el número de caminos entre nodos de un grafo conexo”.

Comienzo con una breve explicación del método que he empleado:

Este problema puede ser resuelto mediante una búsqueda en profundidad en el grafo, el algoritmo es bastante rápido y sirve para cualquier tamaño de grafo (mi solución es recursiva y, para un grafo de tamaño n siendo n muy grande produciría un desbordamiento de pila, aunque ese problema no se nos presentará en esta practica ya que n es menor que 100).

Dejo un link a la práctica entera, esta vez es mi solución con el apartado 1 actualizado, respecto al apartado 2 recomiendo usar el de nuestro compañero David ubicado en el post: http://alejandromoran.com/practica-algoritmica-y-complejidad/

Link al fichero .adb: Fichero .adb comprimido

Y a continuación dejo el código de la práctica para verlo en esta entrada del blog:

Tagged with: , , , ,
8 comments on “Número de caminos entre nodos de un grafo
  1. Mario says:

    Muchas gracias Alejandro por el esfuerzo de ayudarnos.
    Esta todo bien de la practica salvo por el apartado 2 =O
    Dado que el resultado que se escribe en el fichero salida2.txt
    no corresponde con los que ponen en la practica.
    Aun así muchísimas gracias por tu tiempo de verdad.
    Un saludo!

  2. Mario says:

    Se me había olvidado ponerte lo que surge en el apartado 2:
    Lo que hay en el fichero entrada.txt
    5
    1 2 2
    1 3 2
    1 4 3
    2 5 1
    3 5 4
    4 5 1

    Lo que se obtiene el fichero apartado2.txt:
    5
    1 4 3
    1 2 2
    1 3 2
    3 5 4
    En vez de esto que es lo que se supone que tendría que salir:
    5
    1 2 2
    1 3 2
    1 4 3
    3 5 4

    Gracias de nuevo!

    • AlejandroMoran says:

      Buenas Mario, el año pasado ya me enfrenté yo a eso que preguntas, en realidad está bien salvo que la ejecución del algoritmo mío ha tomado un camino distinto al de la solución propuesta, pregúntale a tu profesor si existe algún problema, en mi caso el año pasado no lo hubo, y no debería de haberlo ya que es un camino igualmente válido, mi algoritmo se basa en el de PRIM, pero tomando caminos de valor máximo, un saludo.

      • Mario says:

        A vale,mientras que sea un árbol recubridor mínimo no pasa nada por el algoritmo de Prim!
        Una vez mas gracias por todo!
        Un saludo!

  3. Daniel says:

    Hola Alejandro, primero de todo, agradecerte por el trabajo que haces y ayudarnos a todos.

    Mi pregunta es que si lo que hay en esta página está todo bien y optimizado, o es mejor hacer un “mix” con un apartado de aquí y el que hizo tu compañero David. Si es así que me recomendarías?

    Un saludo y gracias

    • AlejandroMoran says:

      Buenas Daniel, perdona por tardar en responder, ya sabes que en las últimas semanas se acumula mucho trabajo 🙂 mi recomendación es hacer un buen “mix” de las dos prácticas pq según dicen este año tienen “anticopia” (que lo dudo un poco) y aún así me consta que mucha gente se ha basado en estas prácticas para entregar la suya propia así que lo mejor que puedes hacer es una buena mezcla de las dos, un saludo 🙂

  4. Carlos says:

    Alejandro hay alguna forma de hacer el apartado 1 con el numero de caminos entre los nodos de un grafo ,con la forma de hacerlo de David?

    • AlejandroMoran says:

      El algoritmo desarrollado en la práctica de David es el “Algoritmo de Floyd-Warshall”, únicamente sirve para encontrar el camino mínimo entre dos nodos en grafos ponderados. Si quieres hacer ese apartado, te recomiendo realizar una búsqueda por internet, el que yo hice está basado en un algoritmo conocido muy fácil de implementar, no recuerdo el nombre, solamente que lo encontré en Java y lo adapté a mi código, un saludo!.

1 Pings/Trackbacks for "Número de caminos entre nodos de un grafo"
  1. […] Número de caminos entre nodos de un grafo […]

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.