algorithm - que - notacion de grafos

Enumerando todas las rutas en un gráfico acíclico dirigido

Question

¿Hay algún algoritmo estándar que encuentre todas las rutas posibles en un gráfico dirigido a cíclico? Si no, ¿cómo puedo hacer cambios en BFS / Dijkstra / cualquier otro algoritmo para enumerar todas las rutas en un DAG

Answer 1

Aquí hay un ejemplo corto de python de un DFS modificado para lograr esto:

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5]}

def dfs(data, path, paths = []):   
    datum = path[-1]              
    if datum in data:
        for val in data[datum]:
            new_path = path + [val]
            paths = dfs(data, new_path, paths)
    else:
        paths += [path]
    return paths

Entrada:

print dfs(data = data, path = [1], paths = []) # adjacency list; a list containing the node to start from; and initialize an empty list for all possible paths

Salida:

[[1, 2, 3, 4, 5], 
[1, 2, 3, 5], 
[1, 3, 4, 5], 
[1, 3, 5]]

Answer 2

Encontrar todos los caminos posibles en cualquier gráfico en exponencial. Se puede resolver usando Backtracking. Para los DAG, podemos hacerlo utilizando la primera búsqueda de profundidad (DFS). En el código DFS, comience en cualquier nodo, vaya a la ruta extrema del callejón sin salida y anote todos los nodos visitados en esa ruta usando algún arreglo o lista. Tan pronto como encuentre un callejón sin salida, imprima la matriz que contiene los nodos visitados y muestre el último nodo almacenado y comience en la otra ruta del (n-1) thno nodo. Si todas las rutas del nodo (n-1) th se agotan, saque ese nodo de la lista y comience en (n-2) nodo. Haga esto hasta llegar a todos los callejones sin salida y llegar al primer nodo. Todas las rutas impresas son las rutas en el DAG dado.

Puede consultar el código http://pastebin.com/p6ciRJCU