Encuentra las rutas entre dos nodos dados?

Supongamos que tengo nodos conectados de la siguiente manera, ¿cómo llego al número de rutas que existen entre los puntos dados y los detalles de la ruta?

1,2 //node 1 and 2 are connected 2,3 2,5 4,2 5,11 11,12 6,7 5,6 3,6 6,8 8,10 8,9 

Encuentra los caminos del 1 al 7:

Respuesta: 2 caminos encontrados y son

 1,2,3,6,7 1,2,5,6,7 

texto alternativo

la implementación que se encuentra aquí es agradable, voy a usar la misma

Aquí está el fragmento del enlace de arriba en python

 # a sample graph graph = {'A': ['B', 'C','E'], 'B': ['A','C', 'D'], 'C': ['D'], 'D': ['C'], 'E': ['F','D'], 'F': ['C']} class MyQUEUE: # just an implementation of a queue def __init__(self): self.holder = [] def enqueue(self,val): self.holder.append(val) def dequeue(self): val = None try: val = self.holder[0] if len(self.holder) == 1: self.holder = [] else: self.holder = self.holder[1:] except: pass return val def IsEmpty(self): result = False if len(self.holder) == 0: result = True return result path_queue = MyQUEUE() # now we make a queue def BFS(graph,start,end,q): temp_path = [start] q.enqueue(temp_path) while q.IsEmpty() == False: tmp_path = q.dequeue() last_node = tmp_path[len(tmp_path)-1] print tmp_path if last_node == end: print "VALID_PATH : ",tmp_path for link_node in graph[last_node]: if link_node not in tmp_path: #new_path = [] new_path = tmp_path + [link_node] q.enqueue(new_path) BFS(graph,"A","D",path_queue) -------------results------------------- ['A'] ['A', 'B'] ['A', 'C'] ['A', 'E'] ['A', 'B', 'C'] ['A', 'B', 'D'] VALID_PATH : ['A', 'B', 'D'] ['A', 'C', 'D'] VALID_PATH : ['A', 'C', 'D'] ['A', 'E', 'F'] ['A', 'E', 'D'] VALID_PATH : ['A', 'E', 'D'] ['A', 'B', 'C', 'D'] VALID_PATH : ['A', 'B', 'C', 'D'] ['A', 'E', 'F', 'C'] ['A', 'E', 'F', 'C', 'D'] VALID_PATH : ['A', 'E', 'F', 'C', 'D'] 

La búsqueda de primer orden atraviesa un gráfico y, de hecho, encuentra todas las rutas desde un nodo inicial. Por lo general, BFS no mantiene todas las rutas, sin embargo. En cambio, actualiza una función predecesora π para guardar la ruta más corta. Puede modificar fácilmente el algoritmo para que π(n) no solo almacene un predecesor sino una lista de posibles predecesores.

Entonces, todas las rutas posibles se codifican en esta función y, al recorrer π recursivamente, se obtienen todas las posibles combinaciones de ruta.

Un buen pseudocódigo que utiliza esta notación se puede encontrar en Introducción a los algoritmos por Cormen et al. y posteriormente se ha utilizado en muchos guiones de la Universidad sobre el tema. Una búsqueda en Google de “predecesor de pseudocódigo BFS π” desencadena este hit en Stack Exchange .

Para aquellos que no son expertos PYTHON, el mismo código en C ++

 //@Author :Ritesh Kumar Gupta #include  #include  #include  #include  #include  #include  using namespace std; vector >GRAPH(100); inline void print_path(vectorpath) { cout<<"[ "; for(int i=0;ipath) { for(int i=0;ipath; path.push_back(source); queue >q; q.push(path); while(!q.empty()) { path=q.front(); q.pop(); int last_nodeof_path=path[path.size()-1]; if(last_nodeof_path==target) { cout<<"The Required path is:: "; print_path(path); } else { print_path(path); } for(int i=0;inew_path(path.begin(),path.end()); new_path.push_back(GRAPH[last_nodeof_path][i]); q.push(new_path); } } } return 1; } int main() { //freopen("out.txt","w",stdout); int T,N,M,u,v,source,target; scanf("%d",&T); while(T--) { printf("Enter Total Nodes & Total Edges\n"); scanf("%d%d",&N,&M); for(int i=1;i<=M;++i) { scanf("%d%d",&u,&v); GRAPH[u].push_back(v); } printf("(Source, target)\n"); scanf("%d%d",&source,&target); findpaths(source,target,N,M); } //system("pause"); return 0; } /* Input:: 1 6 11 1 2 1 3 1 5 2 1 2 3 2 4 3 4 4 3 5 6 5 4 6 3 1 4 output: [ 1 ] [ 1 2 ] [ 1 3 ] [ 1 5 ] [ 1 2 3 ] The Required path is:: [ 1 2 4 ] The Required path is:: [ 1 3 4 ] [ 1 5 6 ] The Required path is:: [ 1 5 4 ] The Required path is:: [ 1 2 3 4 ] [ 1 2 4 3 ] [ 1 5 6 3 ] [ 1 5 4 3 ] The Required path is:: [ 1 5 6 3 4 ] */ 

El algoritmo de Dijkstra se aplica más a las rutas ponderadas y parece que el póster quería encontrar todas las rutas, no solo las más cortas.

Para esta aplicación, construiría un gráfico (su aplicación parece que no necesitaría ser dirigida) y usaría su método de búsqueda favorito. Parece que quieres todos los caminos, no solo adivinar el más corto, así que utiliza un algoritmo recursivo simple de tu elección.

El único problema con esto es si el gráfico puede ser cíclico.

Con las conexiones:

  • 1, 2
  • 1, 3
  • 2, 3
  • 2, 4

Mientras busca un camino de 1-> 4, podría tener un ciclo de 1 -> 2 -> 3 -> 1.

En ese caso, entonces mantendría una stack atravesando los nodos. Aquí hay una lista con los pasos para ese gráfico y la stack resultante (lo siento por el formato, no hay opción de tabla):

nodo actual (posibles nodos siguientes menos de donde venimos) [stack]

  1. 1 (2, 3) [1]
  2. 2 (3, 4) [1, 2]
  3. 3 (1) [1, 2, 3]
  4. 1 (2, 3) [1, 2, 3, 1] // error – número duplicado en la stack – ciclo detectado
  5. 3 () [1, 2, 3] // retrocedió al nodo tres y sacó 1 de la stack. No más nodos para explorar desde aquí
  6. 2 (4) [1, 2] // retrocedió al nodo 2 y sacó 1 de la stack.
  7. 4 () [1, 2, 4] // Nodo de destino encontrado – stack de registros para una ruta. No más nodos para explorar desde aquí
  8. 2 () [1, 2] // retrocedió al nodo 2 y sacó 4 de la stack. No más nodos para explorar desde aquí
  9. 1 (3) [1] // retrocedió al nodo 1 y sacó 2 de la stack.
  10. 3 (2) [1, 3]
  11. 2 (1, 4) [1, 3, 2]
  12. 1 (2, 3) [1, 3, 2, 1] // error – número duplicado en la stack – ciclo detectado
  13. 2 (4) [1, 3, 2] // retrocedió al nodo 2 y sacó 1 de la stack
  14. 4 () [1, 3, 2, 4] Nodo de destino encontrado: stack de registros para una ruta. No más nodos para explorar desde aquí
  15. 2 () [1, 3, 2] // retrocedió al nodo 2 y sacó 4 de la stack. No más nodos
  16. 3 () [1, 3] // retrocedió al nodo 3 y extrajo 2 de la stack. No más nodos
  17. 1 () [1] // retrocedió al nodo 1 y sacó 3 de la stack. No más nodos
  18. Hecho con 2 rutas registradas de [1, 2, 4] y [1, 3, 2, 4]

El código original es un poco engorroso y es posible que desee utilizar las colecciones.deque en su lugar si desea utilizar BFS para encontrar si existe una ruta entre 2 puntos en el gráfico. Aquí hay una solución rápida que pirateé:

Nota: este método puede continuar infinitamente si no existe una ruta entre los dos nodos. No he probado todos los casos, YMMV.

 from collections import deque # a sample graph graph = {'A': ['B', 'C','E'], 'B': ['A','C', 'D'], 'C': ['D'], 'D': ['C'], 'E': ['F','D'], 'F': ['C']} def BFS(start, end): """ Method to determine if a pair of vertices are connected using BFS Args: start, end: vertices for the traversal. Returns: [start, v1, v2, ... end] """ path = [] q = deque() q.append(start) while len(q): tmp_vertex = q.popleft() if tmp_vertex not in path: path.append(tmp_vertex) if tmp_vertex == end: return path for vertex in graph[tmp_vertex]: if vertex not in path: q.append(vertex) 

En Prolog (específicamente, SWI-Prolog)

 :- use_module(library(tabling)). % path(+Graph,?Source,?Target,?Path) :- table path/4. path(_,N,N,[N]). path(G,S,T,[S|Path]) :- dif(S,T), member(SI, G), % directed graph path(G,I,T,Path). 

prueba:

 paths :- Graph = [ 1- 2 % node 1 and 2 are connected , 2- 3 , 2- 5 , 4- 2 , 5-11 ,11-12 , 6- 7 , 5- 6 , 3- 6 , 6- 8 , 8-10 , 8- 9 ], findall(Path, path(Graph,1,7,Path), Paths), maplist(writeln, Paths). ?- paths. [1,2,3,6,7] [1,2,5,6,7] true.