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.

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 

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

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

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.