Foro de elhacker.net

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.

Sólo necesitas realizar dos Dijkstras: uno desde el inicio del primer hombre al resto del grafo y otro des del segundo hombre al resto del grafo, teniendo en cuenta en cada caso los arcos válidos para cada uno. Así, tendrás la mínima distancia a cada nodo del grafo respecto cada inicio. Basta ahora que iteres sobre los nodos: si un nodo se puede alcanzar desde ambos extremos, se pueden encontrar en tiempo la suma de las distancias mínimas hasta ese nodo. Coges el mínimo de todos los vértices y es la solución, si no me equivoco.

Además, si los arcos no tienen costes, puedes usar un BFS en lugar de un Dijkstra, haciendo que el problema sea resuelto en complejidad lineal sobre el tamaño del grafo.

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!