Partage
  • Partager sur Facebook
  • Partager sur Twitter

Algorithme Dijkstra sous java

    13 mai 2020 à 20:54:38

    Salut, je veux implementer l'algorithme de Dijkstra qui calcule le chemin le plus court probleme c'est que jen e sais pas par ou commencer j'ai deje implementer le graphe avec les noueds et les successeurs amis je ne sais pas si je dois creer une nouvelle classe si oui comment ou la rediger comme etant une methode a l'interieure de la classe graphe. SVP c'est une devoir note et je ne sais pas par ou commencer.

    • Partager sur Facebook
    • Partager sur Twitter
      14 mai 2020 à 8:42:49

      Bonjour 

      https://www.codeflow.site/fr/article/java-dijkstra voici un lien qui pourra t'inspirer à comprendre si ça peut t'aider 

      en ce qui concerne le plus court chemin tu peux creer une seule classe djikstra ou tu recuperera ton graphe avec une methode et calculer

      le plus court chemin avec une deuxième méthode 

      • Partager sur Facebook
      • Partager sur Twitter
        23 mai 2020 à 7:39:28

        Bonjour, merci pour ta reponse j'ai essaye de faire ce que vous avez j'ai cree la classe impleemente la methode du chemin le plus court mais j'ai une un message d'erreur que je n'arrive pas a resourdre. Il m'affiche : Exception in thread "main" java.lang.NullPointerException

        at successeur.Dijkstra.chemin_court(Dijkstra.java:81)
        at successeur.testSuc.main(testSuc.java:42)
        

        -
        Edité par chaimaamooutachaouiq 23 mai 2020 à 7:43:57

        • Partager sur Facebook
        • Partager sur Twitter
          23 mai 2020 à 9:16:07

          C'est que la ligne 81 de la classe Dijstra reçoit un objet null, il faut utiliser le debugger de l'ide pour savoir pourquoi.
          • Partager sur Facebook
          • Partager sur Twitter
            25 mai 2020 à 0:18:55

            package successeur;
            import java.util.*;
            /*le probleme que j'ai maintenant c'est que je n'arrive pas a creer la methode 
             * qui va me permettre de trouver le chemin ou je vais entrer mon noeud de depart
             * et destination et afficher le chemin le plus court a suivre 
             */
            
            public class Dijkstra{
            	
            	    private HashSet<noeud> Q= new HashSet<noeud>();//Complement de P
            		private Map <noeud,Integer> poids = new HashMap <noeud,Integer>();
            		private Map <noeud,noeud> precedent= new HashMap<>();
            		List <noeud> visite= new ArrayList<noeud>();
            		
            		
            	public int q=(int) Double.MAX_VALUE;
            	
            	public Dijkstra(graphe g, noeud nd, noeud nf)
            	{
            		//Initialisation
            		poids.put(nd, 0);//noeud de depart
            		Q.add(nd);
            		for(noeud o:g.getListnoeuds())
            		{
            			if(o.num!=nd.num)
            			{
            				poids.put(o,q);
            				Q.add(o);
            			}
            		}
            	}	
            	
            	
            	private int key;
            	public void chemin_court(graphe g,noeud n1)
            	{
            		while(!Q.isEmpty())
            		{
            			//Trouver min dans Q
            			int s=-1;
            			for(noeud o: Q)
            			{
            				if(!visite.contains(o))
            				{
            					if(poids.get(o)<q) 
            					{
            						q=poids.get(o);
            						s=o.num;
            					}
            					
            					for(successeur v:o.getListSucc()) 
            					{
            						int chemin=poids.get(o)+o.distance(v.getnoeud());
            				        if(chemin < poids.get(v.getnoeud()))
            				        {
            				        	poids.put(v.getnoeud(), chemin);
            				        	precedent.put(o,v.getnoeud());//(From,To)
            				        }
            					}
            				}
            				visite.add(o);
            				Q.remove(o);
            		   }
            		}
            }
            	
            /* VOILA LA METHODE QUI AFFICHE LE CHEMIN LE PLUS COURT
             * A PARTIR DE nd (noeud de depart) nf (noeud d'arrive)
             */
            	
            	public void path(graphe g, noeud  nd, noeud nf)
            	{
            		noeud n=nf;
            		List<Integer> resultat = new ArrayList<Integer>();
            		
            	}
            	
            	public int getKey() {
            		return key;
            	}
            
            	public void setKey(int key) {
            		this.key = key;
            	}
            			
            }
            

            -
            Edité par chaimaamooutachaouiq 25 mai 2020 à 2:07:02

            • Partager sur Facebook
            • Partager sur Twitter
              2 juin 2020 à 13:22:08

              Salut j'ai essaye d'implementer le programme en utilisant PriorityQueue mais il m'affiche toujours l'erreur suivante :

              Exception in thread "main" java.lang.ClassCastException: successeur.noeud cannot be cast to java.lang.Comparable

              at java.util.PriorityQueue.siftUpComparable(Unknown Source)
              at java.util.PriorityQueue.siftUp(Unknown Source)
              at java.util.PriorityQueue.offer(Unknown Source)
              at java.util.PriorityQueue.add(Unknown Source)
              at successeur.dijkstra1.chemin_court(dijkstra1.java:66)
              at successeur.testSuc.main(testSuc.java:45)
              

              Voila le programme: https://hasteb.in/igizimih.cs Aidez moi SVP je n'arrive pas a trouver l'erreur.

              • Partager sur Facebook
              • Partager sur Twitter
                2 juin 2020 à 14:02:30

                La classe noeud n’implémente probablement pas Comparable.
                • Partager sur Facebook
                • Partager sur Twitter

                Algorithme Dijkstra sous java

                × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                • Editeur
                • Markdown