Chemin le plus court et graphe
Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Chemin le plus court et graphe



  1. #1
    Mcflys

    Chemin le plus court et graphe


    ------

    Bonjour à toutes et à tous !

    Je suis en train de travailler sur l'algorithme de plus court chemin (un noeud vers tous les autres noeuds) dans le cas des graphes (aussi connu sous le nom : "Algorithme de Dijkstra").

    J'ai déjà cherché les pseudo code et essayer de comprendre comment cet algorithme fonctionne.
    Mon problème se situe au niveau de l'implémentation en Java.
    Le chemin obtenu à l'exécution n'est pas le bon, ce qui me frustre beaucoup car je n'arrive pas à le corriger.
    Pouvez vous m'aider ?

    Globalement, j'ai deux vecteurs, Initial qui contient l'ensemble des noeuds de mon graphe et Solution qui contient les noeuds dans l'ordre du parcours le plus court. Donc au fur et à mesure, je parcours, je supprime les noeuds plus cours et l'ajoute dans le vecteur solution. Quand le vecteur Initialest vide, cela sera fini et j'aurais parcouru en entier le graphe.
    J'ai commenté mon code et mis des variables au nom explicite pour une meilleur compréhension (pièce jointe)


    J'utilise 4 classes:
    * graphe (construit le graphe et implement dijkstra)
    * Liste (Liste d'adjacence)
    * noeud (créer un noeud)
    * test



    Voici un exemple de Graphe graphe.jpg

    J'ai implémenté ce graphe directement dans mon programme (vous n'avez donc qu'à exécuter).

    J'obtiens en résultat :
    A partir du noeuds S0, la plus petite distance pour aller au noeuds
    0 est 0
    1 est 11
    2 est 18
    3 est 11
    4 est 18
    5 est 9999 (Infini)

    Logiquement, j'aurais du obtenir :
    A partir du noeuds S0, la plus petite distance pour aller au noeuds
    0 est 0
    1 est 2
    2 est 5 (par S1 et S4)
    3 est 7 (par S1 et S4)
    4 est 3
    5 est 9999 (Infini)

    Je vous remercie d'avance pour votre aide

    -----
    Fichiers attachés Fichiers attachés

  2. #2
    JPL
    Responsable des forums

    Re : Chemin le plus court et graphe

    Pour la commodité de la consultation met tes programmes en utilisant la balise Code (# dans la barre d'outils). Merci.
    Dernière modification par JPL ; 27/05/2012 à 15h21.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  3. #3
    Mcflys

    Re : Chemin le plus court et graphe

    Bonjour,

    En fait, je les avais mis en pièce jointe pour éviter de faire un message trop long.
    Mais je les mets avec la balise Code si vous voulez.


    *Classe graph :

    Code:
    import java.util.Vector;
    
    public class graph {
    	
    	public Liste adjacence[]; 
    
    	 
    	graph(int nb_sommets, int nb_arcs){ 
    		adjacence = new Liste[nb_sommets]; 
    		for (int i = 0; i < nb_sommets; i++) 
    			adjacence[i] = null; 
    	} 
    
    	
    	
    	public void afficher() {  //pour afficher le graphe
    		
    		for (int i = 0; i < adjacence.length; i++){ 
    			System.out.print("sommet "+i+" : "); 
    			if (adjacence[i]!=null) { 
    				Liste tmp2 = adjacence[i]; 
    				while(tmp2!=null) { 
    					System.out.print(tmp2.num_noeud + " " + tmp2.valeur + " ");
    					if (tmp2.suivant != null) 
    						System.out.print(tmp2.suivant.num_noeud + " -> "); 
    					tmp2 = tmp2.suivant; 
    				} 
    			}
    			System.out.println(" null");
    		}
    	}
    
    		
    	public boolean arc (int source, int dest){ 	//vérifie s'il y a un arc entre deux noeuds
    		boolean Existe=false; 
    		Liste temporary=adjacence[source];
    		
    		while(temporary!=null){
    			if(temporary.num_noeud==dest){
    				Existe=true; 
    			}	
    			temporary=temporary.suivant;
    		}
    		
    		return Existe; 
    	} 
    
    	
    	public int v_arc(int source, int dest){ //retourne la valeur de l'arc entre les deux noeuds
    		int Val = 999999;
    		if(arc(source, dest)){
    			Val=adjacence[source].valeur;
    		}
    		
    		
    		
    		return Val; 
    	} 
    	
    
    public Vector dijkstra(int num_sommet){ 
    		
    		final int INF = 99999; 		//Inf correspond à l'Infini, c'est à dire qu'il n'y a pas d'arc entre les deux noeuds considérés
    		
    		Vector Solution = new Vector(); //vector Solution qui contient le plus petit parcours selon dijkstra 
    		Vector Initial = new Vector(); //vector Initial qui contient l'ensemble des noeuds
    		
    		//L'objectif est de considérer le noeuds le plus court par rapport au noeud courant, l'ajouter à Solution et le supprimer au Vector Initial au fur et à mesure
    		//Lorsque le vecteur Initial est vide, on aura parcourus l'ensemble du graphe
    		
    		
    		for (int i = 0; i < adjacence.length; i++){ // étape 1 : phase d'initialisation selon Dijkstra à l'infini
    			if (i!=num_sommet) Initial.addElement(new noeud(i,INF)); 
    			else Initial.addElement(new noeud(i,0)); 
    		} 
    		System.out.println("S:"); 
    		for (int i = 0; i < Solution.size(); i++){ //affiche le vecteur Solution
    			System.out.println(((noeud)Solution.elementAt(i)).sommet+", "+((noeud)Solution.elementAt(i)).distance); 
    		} 
    	
    		
    			int poids=INF; //initialisation
    			int indice=0;
    			Liste tmpp=adjacence[num_sommet];
    			
    			//étape 2 : parcours pour trouver le noeud avec la plus petite distance du noeud courant
    			
    		while(!Initial.isEmpty()){
    			while(tmpp!=null){
    				if (poids>tmpp.valeur){
    					poids=tmpp.valeur;
    					indice=num_sommet;
    					}
    				tmpp=tmpp.suivant; 
    			  }
    			
    				poids=INF;//on remet poids= INF pour la prochaine boucle
    				
    					int dn = ((noeud) Initial.elementAt(indice)).distance; //on reconstitue le noeud avec la plus petite distance
    					int sn = ((noeud)Initial.elementAt(indice)).sommet;
    					noeud n=new noeud (sn,dn); 
    					Solution.addElement(n); // ajout
    					Initial.removeElementAt(indice);  //supprime
    					
    					for (int i = 0; i < Initial.size(); i++){  //Parcourir Initial et on vérifie si le chemin est effecivement le plus court
    						noeud y=new noeud(((noeud)Initial.elementAt(i)).sommet,((noeud)Initial.elementAt(i)).distance);
    						if  (arc(n. sommet ,y. sommet )) { 
    							int  d=n. distance +v_arc(n. sommet ,y. sommet ); 
    							if  (d<y. distance ) { 
    							y. distance =d; 
    							Initial.setElementAt(y,i);                          //met à jour les distance
    							
    							}
    						}
    					}
    		}
    		
    	return Solution;// on retourne solution
    	
    	}
    
    public void parcours(){ //construction du graphe
    	
    	adjacence[0]= new Liste(new Integer(1), adjacence[0],new Integer(2)); 
    	adjacence[0]= new Liste(new Integer(3), adjacence[0],new Integer(11)); 
    	adjacence[1]= new Liste(new Integer(2), adjacence[1],new Integer(4)); 
    	adjacence[1]= new Liste(new Integer(4), adjacence[1],new Integer(1)); 
    	adjacence[1]= new Liste(new Integer(3), adjacence[1],new Integer(7)); 
    	adjacence[4]= new Liste(new Integer(3), adjacence[4],new Integer(4)); 
    	adjacence[4]= new Liste(new Integer(2), adjacence[4],new Integer(2)); 
    	adjacence[5]= new Liste(new Integer(3), adjacence[5],new Integer(1)); 
    	this.afficher();
    	
    	 
    } 
    
    
    
    
    }

    *Classe Liste

    Code:
    public class Liste {
    	int num_noeud; 
    	int valeur; 
    	
    	// On utilise les Listes d'adjacences et elles vont indiquer vers quels noeuds pointent le noeud courant 
    
    	Liste suivant; 
    	Liste (int n, Liste t, int v) { 
    		num_noeud=n;
    		valeur=v;
    		suivant=t;
    	}
    	@Override
    	public String toString() {
    		return "S" + num_noeud + ", suivant=" + suivant
    				+ " valeur=" + valeur + "]";
    	}
    	
    
    }
    * Classe noeud
    Code:
    public class noeud {
    	int sommet; 
    	int distance; 
    	noeud(int s, int d){ 
    		sommet=s;
    		distance=d;
    	}
    	@Override
    	public String toString() {
    		return "Element [distance=" + distance + ", S" + sommet + "]";
    	}
    	
    }
    *Classe test
    Code:
    import java.util.Vector;
    
    
    public class test {
    	public static void main(String[] args) {
    		
    		graph h = new graph(6, 8);
    		h.parcours();                 //ici j'initialise mon graphe au préalable avec les sommets et distances initiales
    		
    		Vector Solution=h.dijkstra(0);	//au calcul le plus cours chemin à partir du sommet 0;
    		 for (int i = 0; i < Solution.size(); i++) {
    		 System.out.println(((noeud) Solution.elementAt(i)).sommet + ", " + ((noeud) Solution.elementAt(i)).distance);
    		  }
    		
    	}
    }
    Merci de votre aide

  4. #4
    Mcflys

    Re : Chemin le plus court et graphe

    Personne, si vous avez des questions, je peux essayer de reformuler ?

    Merci

  5. A voir en vidéo sur Futura

Discussions similaires

  1. Plus court chemin
    Par invite7f46329c dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 15/06/2010, 19h40
  2. Graphe: plus long chemin
    Par invitef07d9287 dans le forum Logiciel - Software - Open Source
    Réponses: 4
    Dernier message: 31/10/2009, 18h08
  3. Plus court chemin
    Par invite8a2da01f dans le forum Physique
    Réponses: 1
    Dernier message: 26/05/2009, 11h06
  4. chemin dans un graphe
    Par invite5860fc77 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 02/03/2007, 21h33
  5. Graphe: plus long chemin
    Par oli1978 dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 07/06/2005, 16h51