Tutte le possibili percorsi in un grafo ciclico

Question

sto cercando di sviluppare un algoritmo che identifica tutti i possibili percorsi tra due nodi in un grafico, come in questo esempio:

.

infatti, ho solo bisogno di sapere quali nodi compaiono in tutti i percorsi esistenti.

nel web ha solo riferimenti su DFS, A * o dijkstra, ma penso che in questo caso non funzionino.

Qualcuno sa come risolverlo?

Answer 1

È possibile trovare tutti i percorsi utilizzando DFS come | Vlad descritto. Per trovare quali nodi compaiono in ogni percorso, puoi semplicemente mantenere una matrice di booleani che dice se ogni nodo è apparso in ogni percorso fino a quel momento. Quando il DFS trova un percorso, passare attraverso ogni vertice non nel percorso e impostare il valore dell'array corrispondente su falso. Quando hai finito, solo i vertici con valori di true saranno quelli che appaiono in ogni percorso.

Pseudocodice:

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. 

Tuttavia, questo algoritmo non è molto efficiente. Ad esempio, in un grafico completo di n vertici (tutti i vertici hanno contorni a tutti gli altri) il numero di percorsi sarà n! (n factorial).

Un algoritmo migliore sarebbe quello di verificare l'esistenza in ogni percorso di ogni vertice separatamente. Per ogni vertice, cerca di trovare un percorso dalla sorgente al sink senza andare in quel vertice. Se non riesci a trovarne uno, è perché il vertice appare in ogni percorso.

Pseudocodice:

// 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; 

Purtroppo, questo ha ancora caso peggiore esponenziale durante la ricerca di un percorso. Puoi sistemarlo cambiando la ricerca in una ricerca in ampiezza. Se non sbaglio, questo dovrebbe darti prestazioni O (VE).

Answer 2

Esegui DFS dal nodo iniziale e mantieni il tuo stack che ti dice quali nodi hai visto in un dato momento. Prenditi cura dei cicli: quando hai visto un nodo due volte, hai un ciclo e devi interrompere il percorso corrente. Fare attenzione a non visitare il genitore di un nodo, in modo da evitare cicli di lunghezza 1 (aggiungere un parametro parent alla funzione DFS, sarà di aiuto).

Quindi, quando si raggiunge il nodo di destinazione, restituire il contenuto del proprio stack.

Al termine di DFS, si avranno tutti i percorsi.

Answer 3

Per questo problema, per prima cosa vorrei ottenere l'albero t formato da un DFS su uno dei nodi di destinazione u. Poi, colore tutti i nodi, consente di dire blu, che sono nella sottostruttura s radicata al vostro secondo nodo di destinazione 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. 

Inoltre, Mark V come vero. Infine, userei una funzione ricorsiva fino alle foglie. Qualcosa come

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 
} 

Tutti i nodi contrassegnati come veri sarebbero i tuoi nodi nei percorsi da u a v.Runtime sarebbe al massimo (Vertices + Edges) poiché DFS = (V + E) il massimo per loop (V) il ricorsivo al massimo (V)

Answer 4

un vertice è su un percorso da A a B se è raggiungibile da A e B è raggiungibile da esso.

Quindi: eseguire un riempimento a partire da A. Contrassegnare tutti i vertici. eseguire un riempimento a pieno riempimento partendo da B e seguendo i bordi al contrario. Tutti i vertici contrassegnati che incontri sono parte della soluzione.

Answer 5

So che è passato un po 'di tempo, ma sono venuto qui cercando un algoritmo per trovare All Paths (non solo il percorso più breve) in SQL o Java e ho trovato questo tre (li ho appena postati per mantenere i concetti organizzati):

• Java

  http://introcs.cs.princeton.edu/java/45graph/AllPaths.java.html (dipendenze: Grafico, ST, Set, a, si trovano in http://introcs.cs.princeton.edu/java/45graph/)

• SQL (PostgreSQL).

  check 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'; 
  

  Risultato:

  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 
  

Se si inseriscono nei commenti le righe start with n1... e where n2..., la query restituirà tutti i percorsi in tutto il grafico.