Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Méthode pour éviter de répéter le code de recherche du chemin suite aux recherches par largeur et par profondeur.
- tp2::Chemin retraceChemin(string nomMethode, const tp2::Graphe& graphe,
- const tp2::Coordonnee& arrivee, const tp2::Coordonnee& depart,
- vector<tp2::Coordonnee>& meilleurPrec, vector<tp2::Coordonnee>& listeSommets, int& posDepart,
- int& posArrivee)
- {
- //trouve et trace le chemin du depart a l'arrivee
- tp2::Chemin cheminFinal;
- int nbSommet = listeSommets.size();
- stack<tp2::Coordonnee> cheminInverse;
- vector<tp2::Graphe::PaireSommetCout> listeSommetsAdj;
- tp2::Coordonnee precedent = meilleurPrec[posArrivee];
- tp2::Coordonnee suivant = arrivee;
- cheminInverse.push(arrivee);
- while (precedent != VIDE)//le tableau meilleurPrec a ete initialise au debut
- //avec une variable VIDE...
- {
- bool estTrouve = false;
- cheminInverse.push(precedent);
- for (int i = 0; i < nbSommet && !estTrouve; i++)
- {
- if (precedent == listeSommets[i])
- {
- listeSommetsAdj = graphe.listerSommetsAdjacents(precedent);
- int nbSommetAdj = listeSommetsAdj.size();
- for (int j = 0; j < nbSommetAdj; j++)
- {
- if (listeSommetsAdj[j].coordonnee == suivant)
- {
- cheminFinal.cout = cheminFinal.cout + listeSommetsAdj[j].cout;
- }
- }
- estTrouve = true;
- suivant = precedent;
- precedent = meilleurPrec[i];
- }
- }
- }
- if (cheminInverse.top() != depart)
- {
- return tp2::Chemin();
- }
- else
- {
- while (!cheminInverse.empty())
- {
- tp2::Coordonnee suivant;
- suivant = cheminInverse.top();
- cheminInverse.pop();
- cheminFinal.sequence.push_back(suivant);
- }
- }
- return cheminFinal;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement