Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package successeur;
- import java.util.*;
- public class Dijkstra{
- private List<noeud> Q= new ArrayList<noeud>();
- 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 nd, noeud nf)
- {
- while(!Q.isEmpty())
- {
- //Trouver min dans Q
- for(int i=0;i<Q.size();i++)
- {
- noeud o=Q.get(i);
- if(!visite.contains(o))
- {
- for(successeur v:o.getListSucc())
- {
- int dis=o.distance(g.getnoeud(v.getKey()));
- int chemin=poids.get(o)+dis;
- if(chemin < poids.get(g.getnoeud(v.getKey())))
- {
- poids.put(g.getnoeud(v.getKey()), chemin);
- precedent.put(o,g.getnoeud(v.getKey()));//(From,To)
- }
- }
- }
- visite.add(o);
- Q.remove(o);
- }
- }
- List<Object> resultat = new ArrayList<>();
- noeud n=null;
- n=nf;
- for (Map.Entry<noeud,noeud> entry : precedent.entrySet())
- {
- noeud prev = entry.getKey();
- noeud to = entry.getValue();
- if(n==prev || n!=nd)
- {
- resultat.add(n);
- System.out.println();
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment