Trouver tous les chemins possibles entre deux sommets dans un graphe orienté
Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

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



  1. #1
    TigraoGPB

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


    ------

    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.

    Code:
    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 !!!

    -----
    Dernière modification par gienas ; 19/02/2017 à 18h31. Motif: Ajouté les balises code obligatoires pour les programmes

  2. #2
    Dlzlogic

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

    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.

  3. #3
    TigraoGPB

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

    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é.

  4. #4
    Evil.Saien

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

    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
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  5. A voir en vidéo sur Futura
  6. #5
    Evil.Saien

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

    Citation Envoyé par TigraoGPB Voir le message
    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...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

Discussions similaires

  1. Nombre de chemins dans un graphe complet
    Par V13 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 12/01/2017, 18h41
  2. Egalité de chemins optique entre deux points conjugués
    Par minerva1 dans le forum Physique
    Réponses: 4
    Dernier message: 29/12/2015, 00h53
  3. Recherche de l'ensemble des plus courts chemins entre 2 noeuds d'un graphe
    Par patricia_ze dans le forum Programmation et langages, Algorithmique
    Réponses: 4
    Dernier message: 06/10/2014, 10h00
  4. recherche tous les chemins dans un graphe orienté
    Par invitea5e67aa9 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 11/02/2011, 13h05
  5. Calcul du nombre de chemins possibles dans une grille à 2Dimensions
    Par invitea54a6f54 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 30/06/2009, 19h03