Hola, tengo un compañero en la facultad que fue a dar un parcial de Algoritmos y Estructuras de Datos, mi compañero esta cursando una cursada con promoción por lo que los problemas que les toman son mucho mas difíciles. El otro día me estaba comentando el problema que les tomaron y me pareció bastante curioso y quería ver si sus opiniones concuerdan con la mía en cuanto a la resolución del problema.
El problema era el siguiente: "Alfredo y Omar se encuentran en la ciudad de la esperanza, hace años que no se ven y quieren reencontrarse, Alfredo tiene 25 años y Omar, 40. La ciudad de la esperanza es una ciudad muy particular, ya que tiene calles que solo pueden ser recorridas por mayores de 30 años y otras calles que solo pueden ser recorridas por menores de 30 años (o que tengan 30 años). Las calles también tienen la característica de que algunas se recorren en un sentido y otras, en otro. Implemente un algoritmo que les permita a Alfredo y Omar, encontrarse en un punto de la ciudad que sea el mínimo camino hecho para encontrarse."
Osea tenemos dos personas paradas en dos puntos de un grafo y hay que encontrar un camino para que ambos se encuentren en el grafo que sea el mínimo que tengan que hacer.
Mi idea para resolverlo, explicada muy por arriba, seria, básicamente, hacer un dijkstra de ambos puntos del punto A (Alfredo) al punto O (Omar), modificado para que se pueda adaptar a las particularidades de la ciudad esperanza, luego hacer un dijkstra del punto O al punto A, y ver si coinciden, si no coinciden tendria que buscar el segundo camino mínimo del punto O al punto A que coincida, y así sucesivamente hasta que encuentre uno que coincida. Pero creo que esta idea es un poco, excesivamente complicada, de seguro debe haber un metodo mas sencillo, estos dos tienen que encontrarse en algún punto de la ciudad que sea el punto mas cercano para ambos, ¿pero como determinamos este punto?

Muchas gracias por detenerse a leer.

Gracias, la primer solución es mas o menos como la había pensado. No recuerdo bien si mi compañero me menciono si las calles tenían distancias, pero de no tenerlas claramente la solución con el BFS es mucho mas eficiente.
Saludos!