Guest User

Dijkstra

a guest
May 30th, 2020
257
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.61 KB | None | 0 0
  1. package successeur;
  2. import java.util.*;
  3.  
  4. public class Dijkstra{
  5.    
  6.         private List<noeud> Q= new ArrayList<noeud>();
  7.         private Map <noeud,Integer> poids = new HashMap <noeud,Integer>();
  8.         private Map <noeud,noeud> precedent= new HashMap<>();
  9.        
  10.         List <noeud> visite= new ArrayList<noeud>();
  11.    
  12.         public int q=(int) Double.MAX_VALUE;
  13.        
  14.         public Dijkstra(graphe g, noeud nd, noeud nf)
  15.     {
  16.         //Initialisation
  17.         poids.put(nd, 0);//noeud de depart
  18.        
  19.         Q.add(nd);
  20.         for(noeud o:g.getListnoeuds())
  21.         {
  22.             if(o.num!=nd.num)
  23.             {
  24.                 poids.put(o,q);            
  25.                 Q.add(o);
  26.             }
  27.         }  
  28.  
  29.     }      
  30.     private int key;
  31.     public void chemin_court(graphe g,noeud nd, noeud nf)
  32.     {
  33.         while(!Q.isEmpty())
  34.         {
  35.             //Trouver min dans Q
  36.            
  37.             for(int i=0;i<Q.size();i++)
  38.             {
  39.                 noeud o=Q.get(i);
  40.                 if(!visite.contains(o))
  41.                 {
  42.                     for(successeur v:o.getListSucc())
  43.                     {
  44.                         int dis=o.distance(g.getnoeud(v.getKey()));
  45.                         int chemin=poids.get(o)+dis;
  46.                         if(chemin < poids.get(g.getnoeud(v.getKey())))
  47.                         {
  48.                             poids.put(g.getnoeud(v.getKey()), chemin);
  49.                             precedent.put(o,g.getnoeud(v.getKey()));//(From,To)
  50.                         }
  51.                     }
  52.                 }
  53.                 visite.add(o);             
  54.                 Q.remove(o);
  55.            }   
  56.         }
  57.        
  58.     List<Object> resultat = new ArrayList<>();
  59.     noeud n=null;
  60.     n=nf;
  61.  
  62.      for (Map.Entry<noeud,noeud> entry : precedent.entrySet())
  63.      {
  64.          noeud prev = entry.getKey();
  65.          noeud to = entry.getValue();
  66.          
  67.          if(n==prev || n!=nd)
  68.          {
  69.             resultat.add(n);
  70.             System.out.println();
  71.          }
  72.          
  73.          
  74.      }
  75. }      
  76. }
Advertisement
Add Comment
Please, Sign In to add comment