Trouver tous les chemins possibles entre deux sommets dans un graphe orienté

[invitef94e1e60]

Bonjour à tous,

Je viens d'essayer la méthode avec l'algo proposé mais je n'arrive pas à le faire fonctionner sur java et j'avoue ne pas bien comprendre le déroulement de l'algorithme
pour trouver tous les chemins possibles entre deux points donnés dans un graphe orienté.

A force de me creuser la tête j'ai réussis à trouver une méthode me trouvant un chemin possible mais je n'arrive pas à me servir de la récursivité dans ma méthode pour tous les trouver. Car si mon sommet est marqué alors il n'y repasse pas alors que moi je ne veux pas qu'il repasse par un sommet déjà marqué dans un chemins mais dans les autres chemins, je veux qu'il puisse y retourner ! ^^

Voici mon code :

ma classe hérite d'une classe graphe où dans cette classe se trouve plusieurs méthode comme la liste des successeurs d'un sommet (réc ses prédécesseurs), le nombre de sommets etc.

import java.util.*;

public class Cheminement extends Graphe{

//Vecteur dans lequel je stock mon chemin
private Vector<Integer> tab= new Vector<Integer>();
//tableau de boolean pour marquer un sommet et savoir s'il a déjà été visité
private boolean [] marque = new boolean[1000];


public void chemins(Graphe g, int depart, int arrivee){
int courant = depart;
for(int i=0; i<g.nbSommet(); i++){
marque[i] = false;
}

//Une pile P qui se rempli et se vide au fur et à mesure et permet de sortir de ma boucle while
Stack<Integer> P = new Stack<Integer>();

marque[depart] = true;
P.push(depart);
while(!(P.isEmpty())	&& courant!=arrivee){
courant = P.pop();
tab.add(courant);
for(int i=0; i<g.lst_succ(courant).length; i++){
if(marque[g.lst_succ(courant)[i]] == false){
P.push(g.lst_succ(courant)[i]);
marque[g.lst_succ(courant)[i]] = true;
}//fsi
}//fpour
}//fwhile
}//CheminHami



public java.lang.String toString(){
String str = "chemin : { ";
for(int i=0; i<tab.size(); i++){
str+= tab.get(i) + ", ";
}
str+="}";

return str;
}


public static void main(String[] args) {
Cheminement c1 = new Cheminement();

int A = Graphe.Alpha_NotDef; //Permet de dire qu'il n'y a pas d'arc entre les sommets
int [][]mat = {{A,2,2,A,A,A}, {A,A,A,A,2,A}, {A,2,A,2,A,A}, {A,A,A,A,A,2},{A,A,2,2,A,A}, {A,A,A,A,2,A}}; //Matrice d'adjacence de mon graphe g
Graphe g = new Graphe(mat); //Mon graphe g construit avec le constructeur par matrice

c1.chemins(g, 0, 5); 
System.out.println(c1);	

}
}

Pouriez-vous m'aider, sur mon code, à l'améliorer et me permettre de trouver tous les chemins possibles.


Si je ne nme trompe pas, avec ce graphe (donc avec cette matrice d'adjacence), tous les chemins possibles entre le sommet 0 et le sommet 5 sont :

0; 1; 4; 3; 5
0; 1; 4; 2; 3; 5
0; 2; 1; 4; 3; 5
0; 2; 3; 5


Parce que mon but final est de trouver tous les chemins possible reliant deux sommets passant par tous les sommets du graphe.

Merci BEAUCOUP !!!
-----

[Dlzlogic]

Bonjour,
D'abord, sans indentation, votre code est difficile à lire. Utilisez la balise "[code]".
Je ne connais pas la syntaxe de Java, mais ce n'est qu'un détail.
Vous avez traduit votre algorithme en code Java, si je veux le comprendre, il faudrait que je le dé-traduise.
Avez-vous regardé l'algorithme de Dijkstra ? J'ai bien compris que ce n'est cela que vous cherchez à faire, mais ce serait déjà une petite indication.
Bonne journée.

[invitef94e1e60]

Oui je l'ai déjà regardé et j'ai eu du mal à m'en servir car de ce que j'ai compris c'est par le poids des arcs d'un graphe pondéré.

Or moi, ce n'est pas un graphe pondéré.

[inviteeecca5b6]

Salut,

Je connais assez bien les graphes mais je n'ai pas connaissance d'un algorithm de ce genre pour une raison assez simple, dès que le nombre de noeuds et d'arêtes est au-delà d'une poignée (et quand je dis une poignée c'est à peine 20 noeuds et 30 arêtes), le nombre de possibilités augmente considérablement, si bien qu'il est juste impossible de toutes les lister...

Un chapitre de ce livre (pp 125) traite de ce problème, peut-être y trouveras-tu une solution
http://algo.inria.fr/flajolet/Publications/book.pdf

[A voir en vidéo sur Futura]

[inviteeecca5b6]

A force de me creuser la tête j'ai réussis à trouver une méthode me trouvant un chemin possible mais je n'arrive pas à me servir de la récursivité dans ma méthode pour tous les trouver. Car si mon sommet est marqué alors il n'y repasse pas alors que moi je ne veux pas qu'il repasse par un sommet déjà marqué dans un chemins mais dans les autres chemins, je veux qu'il puisse y retourner ! ^^

Y'a plus qu'à croiser les doigts pour qu'il n'y ait pas de boucles dans le graph alors...