algorithme pour énumérer tous les chemins possibles

Question

Considérons le graphe suivant:

Je suis en train de trouver un moyen d'énumérer tous les chemins possibles à partir d'un noeud source vers un noeud cible. Par exemple, de A à E, nous avons les chemins possibles suivants:

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

Notez que A C D E, il y a en fait 2 chemins, puisque l'un des chemins utilise F3 bord et l'autre utilise bord F5. De plus, comme il y a un cycle entre A et C, vous pourriez vous retrouver avec un nombre infini de chemins, mais pour les besoins de ce que je suis seulement intéressé par des chemins où aucun noeud est répété sur le chemin de la source à la cible.

J'ai écrit un algorithme de recherche en profondeur d'abord (DFS), mais le problème est que lorsque vous avez plusieurs bords Je ne sais pas comment gérer entre 2 noeuds (comme les bords F3 et F5 ci-dessus) il. Mon algorithme apporte uniquement des chemins arrière A C D E et A C E, pas les autres chemins. Dans le cas de A B C E, je comprends la raison, parce qu'il commence à A, puis passe à C et construit les chemins, mais quand le DFS revient au noeud B, il tente alors d'aller à C, mais C a déjà été visité de sorte qu'il se bloque.

Quoi qu'il en soit, je me demandais s'il y avait une façon de faire, ou bien cela est peut-être NP-complet.

Si vous souhaitez voir mon DFS, le code est ci-dessous (désolé pour l'abus macro, j'utiliser dans la programmation du concours il est un peu une habitude).

#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;
}

Sortie:

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

Answer 1

Quoi qu'il en soit, je me demandais s'il y avait une façon de le faire, ou peut-être cela est NP-complet. Je ne crois pas que vous pouvez produire n! chemins possibles en temps polynomiale. Et voilà comment peut vous obtenir si chaque nœud est connecté à l'autre noeud.

mais le problème est que lorsque vous avez plusieurs arêtes entre 2 noeuds (comme les bords F3 et F5 ci-dessus) Donc, vous voulez considérer les bords F3 et F5 être le même, non? Il est probablement l'option la plus simple de supprimer simplement les bords en double avant d'appeler dfs, puis.

parce qu'il commence à A, puis passe à C et construit les chemins, mais quand le DFS revient au noeud B, il tente alors d'aller à C, mais C a déjà été visité il arrête. Eh bien, Marquons C ne pas visité à nouveau, puis.

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

    // do stuff with 'at'

    vis[at] = false;
}

Answer 2

Je pense que le problème de chemin en double sera également manifeste si vous avez par exemple

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

Je pense que votre « nous avons été ici avant » test ne devrait pas il suffit de regarder le nœud actuel, mais le chemin par lequel vous y êtes arrivé. Donc, ne vérifie pas "O", pour vérifier "JMNO" et "JKLO".