Considere el siguiente gráfico:

Estoy tratando de encontrar una manera de enumerar todas las rutas posibles desde un nodo de 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 usa el borde F3 y el otro usa el borde F5. Además, dado que hay un ciclo entre A y C, podría terminar con un número infinito de rutas, pero a los efectos de esto solo me interesan las rutas en las que no se repite ningún nodo en la ruta desde el origen hasta el destino.

Escribí un algoritmo de primera búsqueda de profundidad (DFS), pero el problema es que cuando tienes múltiples bordes entre 2 nodos (como los bordes F3 y F5 anteriores) no estoy seguro de cómo manejarlo. Mi algoritmo solo trae caminos de regresoA C D E yA C E, no los otros caminos. En el caso deA B C E, Entiendo la razón, porque comienza en A y luego va a C y construye esas rutas, pero cuando el DFS vuelve al nodo B, intenta ir a C, pero C ya ha sido visitado, por lo que se detiene.

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

En caso de que desee ver mi DFS, el código está debajo (perdón por el abuso de macro, los uso en la programación de concursos, así que es un poco 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