trabajo con grafos en python

[manuelle]

hola comunidad tengo un problema con grafos, tengo que determinar todos los caminos desde un nodo hacia otro pero en cada camino que aporto debe de haber un nuevo nodo, es decir yo comienzo por el camino minimo entre estos dos nodos(decir que todas las aristas tiene peso 1), despues de determinar este camino minimo debo encontrar todos los otros caminos que me aporten un nodo nuevo que no este en los caminos que voy seleccionando, el problema esta en que no se despues de seleccionar el camino minimo que criterio seguir para ir seleccionando los demas caminos, si alguien tiene alguna idea o un concejo le agradecere la ayuda



saludos manuelle

[razpeitia]

Para la implementación puedes usar "Sencilla implementación de grafos" o puedes usar otra librería.

Ahora para todos los caminos pueden usar backtracking que creo que sería la opción mas directa pero probablemente la menos optima.

El backtrack lo puedes implementar usando búsqueda a lo profundo (DFS) pero obviamente modificando el algoritmo.

También puede que exista un numero infinito de caminos en caso de que tu grafo tenga un ciclo.

Buena suerte con tu tarea.