Todos los posibles caminos en un grafo no dirigido cíclico

Question

estoy tratando de desarrollar un algoritmo que identifica todos los posibles caminos entre dos nodos en un gráfico, como en este ejemplo:

.

de hecho, solo necesito saber qué nodos aparecen en todas las rutas existentes.

en la web solo obtuve referencias sobre DFS, A * o dijkstra, pero creo que no funcionan en este caso.

¿Alguien sabe cómo resolverlo?

Answer 1

Puede encontrar todas las rutas utilizando DFS como describió Vlad. Para encontrar qué nodos aparecen en cada ruta, puede mantener una matriz de booleanos que indique si cada nodo ha aparecido en cada ruta hasta el momento. Cuando su DFS encuentre una ruta, pase por cada vértice no en la ruta y establezca el valor de matriz correspondiente en falso. Cuando hayas terminado, solo los vértices con valores de verdadero serán los que aparezcan en cada ruta.

Pseudocódigo:

int source; 
int sink; 
int nVerts; 
bool inAllPaths[nVerts]; // init to all true 
bool visited[nVerts]; // init to all false 
stack<int> path; // init empty 

bool dfs(int u) 
    if (visited[u]) 
    return; 
    if (u == sink) 
    for i = 0 to nVerts-1 
     if !stack.contains(i) 
     inAllPaths[i] = false; 
    return true; 
    else 
    visited[u] = true; 
    stack.push(u); 
    foreach edge (u, v) 
     dfs(v); 
    stack.pop(); 
    visited[u] = false; 
    return false; 


main() 
    dfs(source); 
    // inAllPaths contains true at vertices that exist in all paths 
    // from source to sink. 

Sin embargo, este algoritmo no es muy eficiente. Por ejemplo, en un gráfico completo de n vértices (todos los vértices tienen bordes para todos los demás), el número de caminos será n. (n factorial).

Un mejor algoritmo sería verificar la existencia en cada camino de cada vértice por separado. Para cada vértice, intente encontrar una ruta desde la fuente al receptor sin tener que ir a ese vértice. Si no puede encontrar uno, es porque el vértice aparece en todos los caminos.

Pseudocódigo:

// Using the same initialisation as above, but with a slight modification 
// to dfs: change the foreach loop to 
foreach edge (u, v) 
    if (dfs(v)) 
    return true; // exit as soon as we find a path 

main() 
    for i = 0 to nVerts-1 
    set all visited to false; 
    if (inAllPaths[i]) 
     visited[i] = true; 
     if (dfs(source)) 
     inAllPaths[i] = false; 
     visited[i] = false; 

Desafortunadamente, esto todavía tiene exponencial peor de los casos en la búsqueda de un camino. Puede solucionar esto cambiando la búsqueda a una búsqueda amplia. Si no me equivoco, esto debería darte el rendimiento O (VE).

Answer 2

Ejecuta DFS desde tu nodo de inicio y mantén tu propia pila que te dice qué nodos has visto en un momento dado. Cuida los ciclos: cuando has visto un nodo dos veces, tienes un ciclo y debes abortar tu ruta actual. Tenga cuidado de no visitar el elemento primario de un nodo, para evitar ciclos de longitud 1 (agregue un parámetro parent a su función DFS, ayudará).

Luego, cuando llegue al nodo de destino, muestre el contenido de su pila.

Una vez que DFS termine, tendrá todas las rutas.

Answer 3

Para este problema, primero obtendría el árbol t formado a partir de un DFS en uno de sus nodos de destino u. Entonces, de color todos los nodos, digamos azul, que están en el subárbol con raíz en su s del segundo nodo destino v.

For each node k in subtree s, 
    if k has an edge to a non-blue node x 
    then k is true and x is true. 

Asimismo, la marca v como verdadero. Finalmente, usaría una función recursiva hasta las hojas. Algo así como

function(node n){ 
    if(n = null) 
     return false 
    if(function(n.left) or function(n.right) or n.val){ 
     n.val = true 
     return true 
    } 
    else 
     return false 
} 

Todos los nodos marcados como verdaderos serían sus nodos en las rutas desde usted hasta v.el tiempo de ejecución sería como máximo (Vértices + Bordes) ya que DFS = (V + E) los bucles for a lo sumo (V) el recursivo como máximo (V)

Answer 4

un vértice está en un camino de A a B si es alcanzable desde A, y B es accesible desde allí.

Por lo tanto: realice un llenado de inundación a partir de A. Marque todos esos vértices. realice un llenado de inundación comenzando desde B y siguiendo los bordes en reversa. Todos los vértices marcados que conoces son parte de la solución.

Answer 5

Sé que ha pasado un tiempo, pero vine aquí en busca de algún algoritmo para encontrar All Paths (no solo el camino más corto) en SQL o Java y encontré este tres (simplemente los publico para mantener organizados los conceptos):

• Java

  http://introcs.cs.princeton.edu/java/45graph/AllPaths.java.html (dependencias: Gráfico, ST, Conjunto, en, se encuentran en http://introcs.cs.princeton.edu/java/45graph/)

• SQL (PostgreSQL).

  Comprobar WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS

  http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/

• PL/SQL (Oracle)

  https://forums.oracle.com/forums/thread.jspa?threadID=2415733

  select pth as "Path", distance as "Distance" 
  from (
      select connect_by_root(n1) || sys_connect_by_path(n2,'>') pth ,n2, level as distance 
      from -- Edge List Table 
      (select 'A' n1,'B' n2 from dual 
      union all select 'A','C' from dual 
      union all select 'B','C' from dual 
      union all select 'B','D' from dual 
      union all select 'D','G' from dual 
      union all select 'C','G' from dual 
      union all select 'D','I' from dual 
      union all select 'C','E' from dual 
      union all select 'E','F' from dual 
      union all select 'F','G' from dual 
      union all select 'F','H' from dual 
      ) links 
      start with n1='A' 
      connect by nocycle prior n2=n1) 
      where n2 = 'G'; 
  

  Resultado:

  Distance Path 
  3 A>B>C>G 
  5 A>B>C>E>F>G 
  3 A>B>D>G 
  2 A>C>G 
  4 A>C>E>F>G 
  

Si pone en los comentarios las líneas start with n1... y where n2... la consulta devolverá todas las rutas en todo el gráfico.