Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. //Méthode pour éviter de répéter le code de recherche du chemin suite aux recherches par largeur et par profondeur.
  2. tp2::Chemin retraceChemin(string nomMethode, const tp2::Graphe& graphe,
  3.       const tp2::Coordonnee& arrivee, const tp2::Coordonnee& depart,
  4.       vector<tp2::Coordonnee>& meilleurPrec, vector<tp2::Coordonnee>& listeSommets, int& posDepart,
  5.       int& posArrivee)
  6. {
  7.    //trouve et trace le chemin du depart a l'arrivee
  8.    tp2::Chemin cheminFinal;
  9.    int nbSommet = listeSommets.size();
  10.    stack<tp2::Coordonnee> cheminInverse;
  11.    vector<tp2::Graphe::PaireSommetCout> listeSommetsAdj;
  12.    tp2::Coordonnee precedent = meilleurPrec[posArrivee];
  13.    tp2::Coordonnee suivant = arrivee;
  14.    cheminInverse.push(arrivee);
  15.    while (precedent != VIDE)//le tableau meilleurPrec a ete initialise au debut
  16.    //avec une variable VIDE...
  17.    {
  18.       bool estTrouve = false;
  19.       cheminInverse.push(precedent);
  20.       for (int i = 0; i < nbSommet && !estTrouve; i++)
  21.       {
  22.          if (precedent == listeSommets[i])
  23.          {
  24.             listeSommetsAdj = graphe.listerSommetsAdjacents(precedent);
  25.             int nbSommetAdj = listeSommetsAdj.size();
  26.             for (int j = 0; j < nbSommetAdj; j++)
  27.             {
  28.                if (listeSommetsAdj[j].coordonnee == suivant)
  29.                {
  30.                   cheminFinal.cout = cheminFinal.cout + listeSommetsAdj[j].cout;
  31.                }
  32.             }
  33.             estTrouve = true;
  34.             suivant = precedent;
  35.             precedent = meilleurPrec[i];
  36.          }
  37.       }
  38.    }
  39.  
  40.    if (cheminInverse.top() != depart)
  41.    {
  42.       return tp2::Chemin();
  43.    }
  44.  
  45.    else
  46.    {
  47.       while (!cheminInverse.empty())
  48.       {
  49.          tp2::Coordonnee suivant;
  50.          suivant = cheminInverse.top();
  51.          cheminInverse.pop();
  52.          cheminFinal.sequence.push_back(suivant);
  53.       }
  54.    }
  55.  
  56.    return cheminFinal;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement