Tengo un gráfico no dirigido, no ponderado, y estoy tratando de llegar a un algoritmo que, dado 2 nodos únicos en el gráfico, encontrará todas las rutas que conectan los dos nodos, sin incluir ciclos. Aquí hay una ilustración de lo que me gustaría hacer: Ejemplo de gráfico
¿Este algoritmo tiene un nombre? ¿Se puede hacer en tiempo polinómico?
Gracias,
Jesse
Para ver las rutas más cortas, consulte la página de Wikipedia del algoritmo Floyd-Warshall
y también:
"An algorithm for computing all paths in a graph" por Lars-Erik Thorelli en BIT Numerical Mathematics, julio de 1966, Volumen 6, Número 4, pp 347-349
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
