Encuentre todas las rutas posibles entre dos nodos en un gráfico no dirigido

¿Alguien puede darme un código C para encontrar todas las rutas posibles entre dos nodos? p.ej. si la gráfica tiene los siguientes bordes 1-2 1-3 2-3 2-4 3-4

Todos los caminos entre 1 y 4 son:

1-2-3-4

1-2-4

1-3-4

1-3-2-4

Una búsqueda en profundidad hace este trabajo.

(Supongo que no desea nodos repetidos en su ruta; de lo contrario, el número de rutas posibles es infinito).

Puedes hacer una relajación:

while (there is a change) { for (v in nodes(G)) { for (e in edges(v)) { paths_to[v] = paths_to[v] union ((paths_to[e.to] not containing v) append v) } } } 

El resultado aún puede ser exponencial en el tamaño del gráfico de entrada. Obtener todos los caminos probablemente no es lo que quieres hacer.

Este es un algoritmo simple para el problema. No es un algoritmo óptimo.

 static struct { int value1; int value2; int used; } data[] = { { 1, 2 }, { 1, 3 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, }; enum { DATA_SIZE = sizeof data / sizeof *data }; static int output[DATA_SIZE]; int traverse(int from, int to, int depth) { output[depth++] = from; int i; if (from == to) { for (i = 0; i < depth; i++) { if (i) { printf("-"); } printf("%d", output[i]); } printf("\n"); } else { for (i = 0; i < DATA_SIZE; i++) { if (!data[i].used) { data[i].used = 1; if (from == data[i].value1) { traverse(data[i].value2, to, depth); } else if (from == data[i].value2) { traverse(data[i].value1, to, depth); } data[i].used = 0; } } } } int main() { traverse(1, 4, 0); } 

Un método recursivo:

 findPaths(path = startNode, goal) paths = [] if the last node in path is goal: return path for each node n connected to the last node in path: if n is not already on the path: paths.append(findPaths(path.append(node), goal)) return paths //may still be [] 

Es demasiado tarde y no es el código C, pero puede ayudar a otros. Este algo muestra cómo lo implemento en java.

 findPath(start) Childs = getDirectChildsOf(start) foreach child in Childs tempRoute; tempRoute.add(start) if (child == end) return tempRoute.add(child) else tempRoute.add(findPath(child)) if (tempRoute.last() == end) return tempRoute; 

Aquí tempRoute puede ser una clase de Route que mantiene una lista de nodos. Capaz de agregar un solo node y otra route a tempRoute . Tampoco encuentra todo el camino posible. para eso tienes que mantener una bandera visitada para cada nodo.