[ Foro de Pascal ]

Camino con menos conexiones(aristas) en un grafo.

Un saludo a todos aquí. Tengo un problema que tengo que resolver y, necesito la ayuda de alguno de ustedes, si me pueden ayudar.
Tengo un grafo no dirigido conexo (las aristas no tienen valor) representado a través de una matriz de adyacencia, y necesito conseguir el camino con menos conexiones (menos aristas) entre un vértice y otro; los vértices destino y final son introducidos por el teclado. Necesito urgentemente hacerlo, ya que me lo van a evaluar. Le estaría muy agradecido a aquel que me pudiera dar una mano en esto. Un fuerte abrazo.

Me temo que llego tarde, pero aun así, opino...

Siempre que se habla de "el menor" o "el mayor", te están dando (casi sin decirlo) un problema de optimización. Si el coste en tiempo o memoria es crítico, se puede atacar con un algoritmo voraz, que dará una solución razonable aunque quizá no óptima; hay muchos tratados que te pueden explicar algoritmos voraces aplicados a grafos; si la solución debe ser óptima, hablamos de bracktracking: probar de todos los caminos que salen desde el primer nodo, luego todos los que salen desde el segundo (de forma recursiva) y asi sucesivamente hasta probar todos los caminos posibles.

Es habitual no usar backtracking puro, sino "ramificación y poda": cortas la recursividad en cuanto sabes que ya no te va a dar resultados mejores. En tu caso, sería no seguir mirando por un camino si su coste ya es mayor que el de la mejor solución que has encontrado hasta el momento.

Muchas gracias por responder, aún estoy a tiempo de hacer el ejercicio.
Yo encontré un algoritmo llamado "Algoritmo de la longitud del camino más corto" que está en el libro "Estructura de Datos" de Luis Joyanes, utiliza un recorrido en anchura. ¿Será efectivo para aplicar en este problema?
Me podría ayudar sobre este problema y su aplicación recursiva, es que la entiendo pero la domino muy poco.
La verdad es que necesito encarecidamente hacer este ejercicio.
Saludos.

Suena razonable. Pon un ejemplo de implementación básica (tanto de tu grafo como del algoritmo), para que podamos ayudarte a partir de ahí con dudas (o errores) puntuales.

Gracias por su respuesta. Sabe que implementé el algoritmo al que le hice mención en un post anterior y, resultó ser la solución que tanto había buscado. Mi tutor lo revisó y, él pensaba que sólo se aplicaba a grafos dirigidos, pero no, también es efectivo para los no dirigidos.
Pero me gustaría hacer la implementación con un método recursivo, como se le ocurrió a usted. ¿Será que me puede dar mayores detalles sobre el mismo?.
Un gran abrazo para usted.