IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Explorer tous les chemins possibles (graphe orienté)


Sujet :

C++

Vue hybride

Mus54Ep Explorer tous les chemins... 19/12/2014, 12h53
ternel Bien sûr qu'on veut voir ton... 19/12/2014, 13h13
Mus54Ep Merci pour votre réponse... 19/12/2014, 14h00
bacelar Actuellement, vos classes Arc... 19/12/2014, 15h04
Mus54Ep bacelar Merci, Donc, je... 19/12/2014, 15h55
Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2014
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Décembre 2014
    Messages : 21
    Par défaut Explorer tous les chemins possibles (graphe orienté)
    Bonjour à tous,
    Et bien, j'ai vraiment besoin d'une idée sur l'exploration de tous les chemins dans un graphe orienté. J'en ai besoin pour terminer mon tp (Plus court chemin).
    J'ai défini un tableau de poids pour tous les arcs. Est-ce que je doit définir encore la matrice d’adjacence ou non ?
    En fait, je sais comment définir la matrice d'adjacence. Cependant, ce que je voudrais savoir c'est une petite idée pour l'exploration.
    Si vous voulez voir le code que j'ai écrit, je le déposerai plus tard.
    Merci d'avance.

  2. #2
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    Bien sûr qu'on veut voir ton code.

    Par contre, tu as regardé du coté de dijsktra (ortographe incertaine)?

  3. #3
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2014
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Décembre 2014
    Messages : 21
    Par défaut
    Merci pour votre réponse
    Contrairement a l'algorithme de Dijkstra (ou Ford-Bellman), le principe de l'optimisation est de parcourir tous les chemins possibles.
    Voila donc le code:

    Code : 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
    24
    #include "stdafx.h"
    #include <iostream>
    #include <vector>
    using namespace std;
     
     
    struct Arc{
    	int pd; //point de départ
    	int pf; // point d'arrivée
    	double poid;
     
    	//Définir le poid de l'arc
    	void setPoid(double pp)
    	{
    		poid = pp;
    	}
     
    	//Définir les 2 sommets
    	void setSommets(int a, int b)
    	{
    		pd = a;
    		pf = b;
    	}
    };

    /*************************************************************************/
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct  Chemin{
    	int sommet;
    	double distance;
    	Chemin*arcSuivant;
    	//Définir la distance
    	void setDistance(double x)
    	{
    		distance += x;
    	}
    };
    Code : 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
    24
    25
    26
    27
    28
    29
    30
    31
    32
     
    int main()
    {
     
    	cout << "Combien de sommet? ";
    	int n;
    	cin >> n;
    	int i = 0, j = 0, k = 0;
    	double poidtemp;
    	vector <Arc> arc;
    	arc.resize(n*n);
    	while (i<n)
    	{
    		while ((k<n*n) && (j<n))
    		{
    			arc[k].setSommets(i + 1, j + 1);
    			cout << endl << "poid[" << i + 1 << "," << j + 1 << "] = ";
    			cin >> poidtemp;
    			arc[k].setPoid(poidtemp);
    			j++;
    			k++;
     
     
    		}
    		j = 0;
    		i++;
    	}
    	for (int i = 0; i<n*n; i++)
    	{
    		arc[i].Afficher();
    	}
    }

  4. #4
    Expert confirmé
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Février 2005
    Messages
    5 502
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : Février 2005
    Messages : 5 502
    Par défaut
    Actuellement, vos classes Arc et Chemin ne proposent rien d'utile.
    Vous pouvez rendre votre code bien plus simple en remplaçant Arc par un simple int dans un std::vector<unsigned int> de taille n*n représentant le poids de l'arc.
    Et en remplaçant Chemin par un std::vector<int> correspondant à la liste des sommets du chemins, sa valeur distance pourra facilement se calculer avec le std::vector<unsigned int> représentant les arc.
    Pour avoir l'ensemble des chemins d'un graphe partant d'un sommet, un simple parcours en profondeur ou en largeur devrait faire l'affaire (à faire sur chaque sommet).

  5. #5
    Membre averti
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2014
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Décembre 2014
    Messages : 21
    Par défaut
    bacelar

    Merci,
    Donc, je doit définir la matrice d'adjacence?

  6. #6
    Expert confirmé
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Février 2005
    Messages
    5 502
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : Février 2005
    Messages : 5 502
    Par défaut
    Sauf erreur de ma part, on vous donne les poids des arcs dans un tableau N*N.
    Si le poids ne peut être null ou négatif, le plus simple, c'est de mettre ces valeurs interdites dans le tableau.
    Ainsi, il n'y a pas de redondance dans les données.
    Pour savoir si un sommet est accessible depuis un autre, il suffira de voir si le poids de l'arc dans le tableau a une valeur valide ou pas.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 2
    Dernier message: 01/06/2013, 01h47
  2. Collecte de tous les chemins possibles
    Par Erable dans le forum Mathématiques
    Réponses: 3
    Dernier message: 26/02/2010, 11h45
  3. Réponses: 0
    Dernier message: 26/05/2009, 01h06
  4. Parcours d'un arbre : examiner tous les chemins possibles
    Par Molos dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 06/04/2009, 17h22
  5. [JGraphT] Obtenir tous les chemin possibles
    Par pmartin8 dans le forum API standards et tierces
    Réponses: 3
    Dernier message: 02/06/2006, 19h26

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo