Algorithme de graphe qui ne s'arrête pas

Algorithme de graphe qui ne s'arrête pas - Java - Programmation

Marsh Posté le 12-12-2008 à 17:24:24    

Bonjour.
 
Alors voila mon problème. Je dispose d'un graphe non-orienté stocké sous la forme de matrice.
Je dois mettre en place sur ce graphe un algorithme permettant de trouver le meilleur chemin MAIS en énumérant tous les chemins possibles (sans repasser sur un chemin déja visité) (donc Dijkstra n'est à mon avis pas adapté).  
J'ai déja pensé à une solution mais celle-ci me pose quelques difficultés :  

Code :
  1. public void methodeUn()
  2. {
  3.  for(int i=0;i<this.nb_sommets;i++)
  4.  {
  5.   for(int j=0;j<this.nb_sommets;j++)
  6.   {
  7.    if(i!=j)
  8.    {
  9.     boolean[] visiteMethodeUn = new boolean[this.nb_sommets];
  10.     String chemin = "";
  11.     profondeurMethodeUn(i+1, j+1, visiteMethodeUn, chemin);
  12.    }
  13.   }
  14.  }
  15. }
  17. private void profondeurMethodeUn(int sommet,int sommet_fin, boolean visiteMethodeUn[], String chemin)
  18. {
  19.  visiteMethodeUn[sommet]=true;
  20.  chemin += " "+sommet;
  21.  for(int i=0; i<nb_sommets;i++)
  22.  {
  23.   if(this.graphe[sommet-1][i] != Graphe.couple_infini && this.graphe[sommet-1][i] != Graphe.couple_zero && !visiteMethodeUn[i])
  24.   {
  25.    if(i+1 == sommet_fin)
  26.    {
  27.     System.out.println(chemin + " "+sommet_fin);
  28.     break;
  29.    }
  30.    else
  31.    {
  32.     profondeurMethodeUn(i+1,sommet_fin,visiteMethodeUn,chemin);
  33.    }
  34.   }
  35.  }
  36. }


 
J'ai tenter d'utiliser une sorte de parcours en profondeur mais qui envoi à chaque fois le tableau de booléen pour savoir si un sommet a déja été visité
(on peut dire qu'un tableau est associé à chaque chemin). Le but est que arrivé à la fin du chemin, celui-ci soit affiché(on stock à chaque étape le numéro du sommet pour cela). Voila je ne vois pas trop pourquoi cela ne marche pas et j'avoue que depuis le temps que je suis sur ce programme, il est fortement possible qu'une petite erreur m'est échappée.
 
Merci de votre aide
 
Cordialement

Reply

Marsh Posté le 12-12-2008 à 17:24:24   

Reply

Marsh Posté le 12-12-2008 à 21:23:43    

bonsoir gorion18 ,j'ai vue votre message,et puisque je cherche un moyen pour déssiner un graphe peut etre vous m'aider dans ma recherche.
j'ai des information que je veux les représentées sous forme d'un graphe ou un réseau;pouvez vous m'envoyé un code pour commencer.  
merci et bon courage.

Reply

Marsh Posté le 12-12-2008 à 21:57:09    

Désolé je ne pense pas pouvoir vous aider sur la partie graphique car mon but est purement algorithmique et je n'effectue donc aucun affichage mise a part sous la forme d'une succession de sommet.
 
En revanche si quelqu'un pense avoir une solution à mon problème je suis preneur.
 
Merci

Reply

Marsh Posté le 13-12-2008 à 07:16:16    

Affiche tous les sommets que parcourt ton algo au fur et à mesure, tu devrais pouvoir voir pourquoi le parcours par en boucle infinie.


---------------
Les aéroports où il fait bon attendre, voila un topic qu'il est bien
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed