Java

Algorithme de graphe qui ne s'arrête pas

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Algorithme de graphe qui ne s'arrête pas

gorion18

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 :

public void methodeUn()
{
for(int i=0;i<this.nb_sommets;i++)
{
for(int j=0;j<this.nb_sommets;j++)
{
if(i!=j)
{
boolean[] visiteMethodeUn = new boolean[this.nb_sommets];
String chemin = "";
profondeurMethodeUn(i+1, j+1, visiteMethodeUn, chemin);
}
}
}
}
private void profondeurMethodeUn(int sommet,int sommet_fin, boolean visiteMethodeUn[], String chemin)
{
visiteMethodeUn[sommet]=true;
chemin += " "+sommet;
for(int i=0; i<nb_sommets;i++)
{
if(this.graphe[sommet-1][i] != Graphe.couple_infini && this.graphe[sommet-1][i] != Graphe.couple_zero && !visiteMethodeUn[i])
{
if(i+1 == sommet_fin)
{
System.out.println(chemin + " "+sommet_fin);
break;
}
else
{
profondeurMethodeUn(i+1,sommet_fin,visiteMethodeUn,chemin);
}
}
}
}

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

Publicité

fleure2008

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.

gorion18

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

el muchacho

Comfortably Numb

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

FORUM HardWare.fr

Programmation

Java

Algorithme de graphe qui ne s'arrête pas

Sujets relatifs
dessiner un graphe	Optimisation algorithme d'érosion
Calculer la complexité temporelle d'un algorithme	déssiner un graphe
[EXCEL/VBA] 'lire' dans un graphe	Recherche un algorithme de cryptage/décryptage costaud
tour de hanoi(algorithme recursif)	Java - Afficher un graphe et rendre interactif
Algorithme	aidez moi pour resoudre cet algorithme
Plus de sujets relatifs à : Algorithme de graphe qui ne s'arrête pas

Page générée en 0.055 secondes