Discussion :

[piotrr]

J'ai un graphe, je veux aller d'un point A à un point B.
Je veux alors dresser la liste de tous les chemins possibles entre ces deux sommets.
J'imagine qu'il faut une fonction récursive mais la récursivité et moi ...

Est ce que quelqu'un connaitrait - il un algo tout fait ?

merci

[cha0s]

tu peut utiliser l'algo de Dijkstra.

[piotrr]

Ok mais je ne veux pas trouver le plus court chemin, je veux juste parcourir tous les chemins possibles.

Merci

[pseudocode]

Tu peux calculer les puissance successives de la matrice d'adjacence, afin de connaitre le nombre de chemins de longueur 'n' entre 2 sommets donnés.

Pour identifier précisement chaque chemin tu peux soit faire le calcul inverse, soit conserver les éléménts de la matrice qui ont servis aux calculs intermédiaires.

[Ulmo]

J'ai un graphe, je veux aller d'un point A à un point B.
Je veux alors dresser la liste de tous les chemins possibles entre ces deux sommets.
J'imagine qu'il faut une fonction récursive mais la récursivité et moi ...

Est ce que quelqu'un connaitrait - il un algo tout fait ?

merci

Il va falloir préciser, parce que si il y a un cycle dans ton graphe, il y aura une infinité de chemins...

[piotrr]

J'ai un graphe non orienté avec des cycles.
Je veux trouver tous les chemins d'un point A à un point B sans passer deux fois par le même sommet.
je veux avoir à la fin une liste de tous les chemins possibles.

merci

[pseudocode]

J'ai un graphe non orienté avec des cycles.
Je veux trouver tous les chemins d'un point A à un point B sans passer deux fois par le même sommet.
je veux avoir à la fin une liste de tous les chemins possibles.

merci

Dans ce cas tu peux faire une exploration complète des chemins, avec une recherche taboo.

[piotrr]

Dans ce cas tu peux faire une exploration complète des chemins, avec une recherche taboo.

Qu'est ce que la recherche "taboo"?
Je n'ai rien trouvé à ce propos.

Merci

[pseudocode]

Qu'est ce que la recherche "taboo"?
Je n'ai rien trouvé à ce propos.

Houla... c'est exxxxxtremement compliqué.

Non, je plaisante. Ca consiste a poser des petits cailloux le long du chemin pour éviter de passer 2 fois au meme endroit. Un petit exemple:

On modélise le graphe

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
// nombre de sommets dans le graphe
int n=5;
 
// matrice d'adjacence du graphe 
int[][] adjacencymatrix = new int[][] {
	new int[] {1,1,1,0,0}, //    1
	new int[] {1,1,1,1,0}, //  / | \
	new int[] {1,1,1,1,0}, // 0  |  3 - 4
	new int[] {0,1,1,1,1}, //  \ | /
	new int[] {0,0,0,1,1}, //    2
};

On définit les quelques variables utilisées par notre algorithme:

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
// stockage du chemin pendant l'exploration recursive
int[] path = new int[n];
 
// verrou pour la recherche taboo (tous initialisés à "false" par défaut)
boolean[] taboo = new boolean[n];
 
// sommets de départ/arrivé souhaités
int source=0;
int target=4;

Et enfin l'algorithme de parcours recursif:

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void explore(int position, int depth) {
	path[depth]=position;
 
	// on est sur le sommet d'arrivé -> fini
	if (position==target) {
		// affiche la solution
		for(int i=0;i<=depth;i++) System.out.print(path[i]+" ");
		System.out.print("\n");
		return;
	}
 
	// sinon...
 
	taboo[position]=true; // on pose un caillou
 
	// on explore les chemins restants
	for(int i=0;i<n;i++) {
		if (adjacencymatrix[position][i]==0 || taboo[i]) continue;
		explore(i,depth+1);
	}
 
	taboo[position]=false; // on retire le caillou
}

on appelle l'algorithme avec "explore(source,0);" pour lui dire de commencer à explorer à partir du noeud 'source'. Ce qui nous donne les 4 chemins possibles entre les sommets "0" et "4":

0 1 2 3 4
0 1 3 4
0 2 1 3 4
0 2 3 4