Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2119 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  [graphe] chemins de longueur <=n

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[graphe] chemins de longueur <=n

n°1275895
ADSLfx
Posté le 02-01-2006 à 15:49:51  profilanswer
 

bonjour, je doit realiser un programme permettant de calculer les plus courts chemins d'un graphe, eventuellement avec une marge supplémentaire tolérée. j'ai donc appliqué dijktra pour trouver le plus court, ainsi que sa longueur, mais pour les autres je patauge un peu, quelqu'un connait il un algo existant pour calculer tous les chemins de longeur <= à une valeur donnée ?

mood
Publicité
Posté le 02-01-2006 à 15:49:51  profilanswer
 

n°1276162
dividee
Posté le 03-01-2006 à 00:14:56  profilanswer
 

Essaie ça:
Avec Dijkstra, on obtient le plus court court chemin d'un sommet du graphe vers tous les autres. C'est une bonne chose qui va nous servir.
Soit D(a,i) le chemin de longueur minimum entre a et i (calculé par Dijkstra) et c(i,j) le poids d'une arêtes entre i et j.
a est le sommet de départ et b le sommet de destination.
 
Partons du sommet de destination b. Soit x le sommet précédent b sur le meilleur chemin. Il y a deux cas possibles:
1) Soit le dernier arc du 2ème meilleur chemin ne provient pas de x, dans ce cas le coût du 2ème meilleur chemin est D'(a,b)=min(D(a,i) + c(i,b)) pour tous les précédents i du sommet b différents de x.
2) Soit le dernier arc est identique et provient de x. Dans ce cas on peut se ramener au problème de trouver le 2ème meilleur chemin vers x. Le coût total jusque b sera alors D'(a,x)+c(x,b) où D'(a,x) est le coût du second meilleur chemin jusque x.
 
Autrement dit, pour chaque sommet du meilleur chemin (sauf l'origine bien sûr), on va essayer de prendre un autre précédent. Parmi tous ces chemins alternatifs, celui de coût le plus faible sera le 2nd meilleur chemin.
 
Pour le 3ème meilleur chemin, je ne suis pas certain à 100% mais je pense que ce sera soit un des chemins alternatifs du meilleur chemin (déjà calculés) ou un chemin alternatif du second meilleur chemin (qu'on obtient de la même façon). Et ainsi de suite pour le 4ème, 5ème, etc...


Message édité par dividee le 03-01-2006 à 00:19:45
n°1276634
ADSLfx
Posté le 03-01-2006 à 23:06:20  profilanswer
 

merci pour la reponse, ça ressemble bien a ce que je pensait, j'utilise le resultat de dijkstra, pour parcourir le graphe a l'envers en verifiant a chaque fois les sommets voisins. par contre apres pour le 1) je ne comprend pas trop, et j'ai l'impression qu'on aura qu'un nombre fixé de chemins, mais il peux y en avoir plein, surtout avec la marge supplémentaire. voici ou j'en suis :
 
 

Citation :

   public void autresChemins(Vector sommets,int matriceArcs[][], int T[][],int d,
                int p,int m,Vector v,int prec) {
     Vector chemin=new Vector();
     for (int i=0; i<v.size(); i++) // on recopie le chemin deja parcouru
      chemin.add(v.elementAt(i));
     
        while(p!=d) {
         chemin.insertElementAt(sommets.elementAt(p),0);
          // cas du cul de sac : si on est revenu en arriere, on arrete
         // le parcours et efface le chemin parcouru
         if (chemin.size()>2 && chemin.elementAt(0)==chemin.elementAt(2)) {
          chemin.removeAllElements();
          break;
         }
         for (int i=0; i<sommets.size(); i++)  
         // un chemin secondaire ne doit pas revenir sur le sommet precedent, ni  
         // suivre le plus court chemin, et avoir un poids pas trop elevé  
          if (matriceArcs[i][p]!=-1 && i!=T[1][p] && i!=prec &&  
             (m>(T[0][i]+matriceArcs[i][p]-T[0][p])))
        {
             m=m-T[0][i]-matriceArcs[i][p]+T[0][p];
             autresChemins(sommets,matriceArcs,T,d,i,m,chemin,p);  
        }      
           prec=p;  
              p=T[1][p];
        }
        chemin.insertElementAt(sommets.elementAt(p),0);
        if (chemin.size()>1)
         for (int i=0;i<chemin.size();i++)
          tousLesChemins.add(chemin.elementAt(i));
    }


 
 
lancé par l'insturction

Citation :

          autresChemins(sommets,matriceArcs,T,pDepart,pArrivee,m*5*T[0][pArrivee]/100,bidon,
                          pArrivee);


 
matriceArcs donne les distances entre les arcs (-1 si non reliés); pDepart est la position de depart, pareil pour l'arrivée; m est la marge; chemin contient un chemin (il y aura donc autant de vecteurs que de resultats; tousLesChemins cntient tous les chemins.
 
la le probleme est le suivant : il oublie certaisn chemins, visiblement ceux pour elsquels on doit parcourir le tableau donné par dijkstra en sens inverse. (on parcous un chemin dans un sens alors que si on part de l'un de ses points, le plus court chemin passe en sens inverse). a part ça ça marche.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  [graphe] chemins de longueur <=n

 

Sujets relatifs
Ford Fulkerson | graphe auxiliaireGraphe Orienté : circuit de x à x
Graphe Orienté : existence chemin longueur k ?[Javascript] longueur de Calque dynamique
Longueur d'une comùande Awk[résolu] pb longueur de chaîne avec dbi:PgPP
[batch] longueur d'une chaine de charselection colonnes sous VBA pour confection graphe
Longueur fixe en sortie d'une requête 
Plus de sujets relatifs à : [graphe] chemins de longueur <=n


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR