algoritmo para enumerar todos los posibles caminos

Question

Considere el siguiente gráfico:

Estoy tratando de encontrar una manera de enumerar todos los posibles caminos desde un nodo origen a un nodo de destino. Por ejemplo, de A a E, tenemos las siguientes rutas posibles:

A B C D E 
A B C E 
A C D E 
A C E 

Tenga en cuenta que para A C D E, en realidad hay 2 caminos, ya que uno de los caminos utiliza F3 borde y el otro utiliza F5 borde. Además, dado que hay un ciclo entre A y C, puede terminar con un número infinito de rutas, pero a los fines de esto, solo me interesan las rutas en las que no se repite ningún nodo en la ruta de la fuente al objetivo.

Escribí un algoritmo de búsqueda profunda (DFS), pero el problema es que cuando tienes varios bordes entre 2 nodos (como los bordes F3 y F5 anteriores) no estoy seguro de cómo manejarlo. Mi algoritmo solo devuelve las rutas A C D E y A C E, no las otras rutas. En el caso de A B C E, entiendo la razón, porque comienza en A y luego va a C y crea esas rutas, pero cuando el DFS vuelve al nodo B, intenta ir a C, pero C ya ha sido visitado. entonces se detiene

De todos modos, me preguntaba si había una manera de hacer esto, o tal vez esto es NP-completo.

En caso de que quiera ver mi DFS, el código está debajo (disculpe el abuso de macros, los utilizo en la programación del concurso, así que es un hábito).

#include <algorithm> 
#include <numeric> 
#include <iostream> 
#include <sstream> 
#include <string> 
#include <vector> 
#include <queue> 
#include <deque> 
#include <set> 
#include <map> 
#include <cstdio> 
#include <cstdlib> 
#include <cctype> 
#include <cassert> 
#include <cmath> 
#include <complex> 
#include <stack> 
#include "time.h" 
using namespace std; 
#define SZ(x) (int)x.size() 
#define FOR(i,x,y) for(int i=(int)(x);i<=(int)(y);++i) 
#define REP(i,n) FOR(i,0,n-1) 
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i) 
#define ALL(a) (a).begin(),(a).end() 
#define FORE(i,t) for(i=t.begin();i!=t.end();++i) 
typedef vector<int> VI; 
typedef vector<string> VS; 
typedef vector<bool> VB; 
typedef vector<double> VD; 
typedef deque<int> DI; 
typedef deque<string> DS; 
typedef long long i64; 
#define PI 3.14159265358979323 
#define DEGTORAD(x) (double)x * 3.14159265358979323846264338327950288/180.0 
#define RADTODEG(x) (double)x * 180/3.14159265358979323846264338327950288 
#define prt if(1)printf 
template <typename T> string tostr(const T& t) { ostringstream os; os<<t; return os.str(); } 

typedef pair< char, char > PCC; 
map< PCC, int > adj; 
map< char, bool > vis; 

vector<char> path; 

void dfs(char at) { 
    if (at == 'E') { 
    REP(i,SZ(path)) { 
     if (i != 0) 
     cout<<","; 
     cout<<path[i]; 
    } 
    cout<<",E"<<endl; 
    return; 
    } 
    if (vis[at]) 
    return; 
    vis[at] = true; 
    map< PCC, int >::iterator it; 
    FORE(it,adj) { 
    if (it->first.first == at) { 
     path.push_back(it->first.first); 
     dfs(it->first.second); 
     path.erase(path.end()-1); 
    } 
    } 
} 


int main() { 
    adj[make_pair('A','B')] = 1; 
    adj[make_pair('A','C')] = 1; 
    adj[make_pair('C','D')] = 1; 
    adj[make_pair('D','E')] = 1; 
    adj[make_pair('E','I')] = 1; 
    adj[make_pair('C','F')] = 1; 
    adj[make_pair('F','G')] = 1; 
    adj[make_pair('F','H')] = 1; 
    adj[make_pair('C','E')] = 1; 
    dfs('A'); 
    return 0; 
} 

Salida:

---------- Capture Output ---------- 
A,C,D,E 
A,C,E 

Answer 1

todos modos, sólo se preguntaba si había una manera de hacer esto, o tal vez esto es NP-completo.
No creo que pueda dar salida a n! posibles rutas en tiempo polinomial. Y así es como puede obtenerse si cada nodo está conectado a cada otro nodo.

pero el problema es que cuando usted tiene múltiples aristas entre 2 nodos (como bordes de la F3 y F5) por encima de
lo tanto, usted desee considerar bordes F3 y F5 a ser lo mismo, ¿verdad? Probablemente sea la opción más simple simplemente eliminar los bordes duplicados antes de llamar al dfs, entonces.

porque comienza en A y luego va a C y crea esas rutas, pero cuando el DFS vuelve al nodo B, intenta ir a C, pero C ya ha sido visitado y se detiene.
Bien, marquemos C como no visitados de nuevo, entonces.

void dfs(char at) { 
    vis[at] = true; 

    // do stuff with 'at' 

    vis[at] = false; 
} 

Answer 2

Mi conjetura es que el problema del camino duplicado también se manifestará si tiene decir

J->K->L->O->T 
J->M->N->O->T 

Creo que su "hemos estado aquí antes" prueba no sólo debe mirar el nodo actual, pero el camino por el que llegaste allí. Así que no busques "O", busca "JMNO" y "JKLO".