|
Entonces lo que buscas es obtener todos los caminos posibles entre un nodo y otro. Y después de dicho conjunto el más optimo?
Si es eso, perdona, es que yo entendía al subconjunto de nodos buscado como la solución.
Umm.. tendría que pensarlo bien. Aunque a primera impresión sería por "fuerza bruta":
Ir recorriendo nodos hasta llegar al destino. Una vez encontrado el camino, volver a repetir el mismo camino y en el nodo anterior virar hacia otro camino (si es viable, claro está) y seguir recorriendo hasta llegar al destino.
Seguir repitiendo el camino mientras se tengan caminos sin explorar, y con el nodo inmediatamente anterior.
Se que no es un método eficiente, habría que pensarlo.
La otra opción, un tanto más complicada es hacer un Disjkstra doble. Repetir Disjsktra desde el principio y a la vez desde el final. La idea es ir avanzando desde ambos extremos y buscando los nodos coincidentes. Si existe en sus conjuntos P() algún nodo es posiblemente de que por allí pase una de las rutas ruta. Repetir el proceso con las puntas condicentes más "alejadas". No se que tan fiable pueda ser esta idea... se me acaba de surgir, y hay que cocinarla mejor porque está un tantito cruda.
Por ahora, eso tengo en mente. Tal vez sirva de algo.
Saludos,
|