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 borde F5 usos. Además, dado que hay un ciclo entre A y C, que podría terminar con un número infinito de caminos, pero para los fines de la presente estoy interesado sólo en caminos en los que se repite ningún nodo en el camino desde el origen al destino.

Me escribió un algoritmo de primera búsqueda en profundidad (DFS), pero el problema es que cuando usted tiene múltiples aristas entre 2 nodos (como bordes de la F3 y F5 arriba) no estoy seguro de cómo manejar la situación. Mi algoritmo de caminos sólo trae de vuelta A C D E y A C E, no los otros caminos. En el caso de A B C E, entiendo la razón, ya que comienza en A y luego pasa a C y construye los caminos, pero cuando el DFS vuelve al nodo B, entonces se trata de ir a C, pero C ya ha sido visitado de modo que se detenga.

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

En el caso de que le gustaría ver a mi DFS, el código está por debajo (lo siento por el abuso macro, yo uso estos en la programación del concurso, así que es un poco de 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 posibles caminos de salida n! en tiempo polinómico. Y así es como se pueden conseguir 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 arriba)
Por lo tanto, usted desea considerar bordes F3 y F5 a ser el mismo, ¿verdad? Es probablemente la opción más sencilla de eliminar sólo los bordes duplicados antes de llamar dfs, a continuación.

ya que comienza en A y luego pasa a C y construye los caminos, pero cuando el DFS vuelve al nodo B, entonces se trata de ir a C, pero C ya ha sido visitado por lo que se detenga.
Bueno, vamos a C marca como no visitado otra vez, 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 por ejemplo

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 tienes ahí. Así que no se echa para "O", de verificación "JMNO" y "JKLO".