function [d_opt,c_opt]=astar(G,s_start,s_end)
%-----------------------------------------------------------------------
% G : Structure du graphe
%
%     G.n    : nb de sommets du graphe.
%
%     G.succ : tableau de cellules (cells) de taille G.n
%               G.succ{k} : tableau contenant les numéros (entiers) des
%                           successeurs du sommet k.
%
%     G.c    : tableau de cellules de taille G.n
%              G.c{k} : tableau des distances (doubles) du sommet k à  
%                       ses successeurs.
%
%     G.xy   : tableau de doubles de taille G.n x 2 contenant les
%              coordonnées géométriques (x,y) des sommets.
%
% s_start : numéro du sommet de départ
%
% s_end   : numéro du sommet d'arrivée.
% 
% En sortie :
% -----------
% d_opt : distance obtenue 
%
% c_opt : chemin trouvé de s_tart à s_end
%-----------------------------------------------------------------------
    Openlist = zeros(G.n,1);    %  -> liste ouverte S
    Closelist = zeros(G.n,1);   %  -> liste fermée Sc
    Fx = zeros(G.n,1); 
    Phix = zeros(G.n,1);
    pred = zeros(G.n,1);
    
    Openlist(s_start) = 1;                    % on met x_0 dans S
    Lx = norm(G.xy(s_start,:)-G.xy(s_end,:)); % Calcul de L(x_0)
    Phix(s_start)=Lx;                         % phi(x_0) = L(x_0)
    
    while nnz(Openlist)>0  % test si le nb d'elements non nuls est >0
        
        % Déterminer les sommets de la liste S 
        indS = find(Openlist == 1);
        % Déterminer le sommet s_current de S qui réalise le min de Phix 
        % parmi tous les sommets de S
        [val,ind]=min(Phix(indS));
        s_current = indS(ind);
        % Enlever s_current de la liste S et ajouter s_current à Sc
        %. . .
        Openlist(s_current)=0;
        Closelist(s_current)=1;
        % tester si s_current = s_end et sortir si c'est le cas (solution
        % trouvée)        
        if s_current==s_end,
            d_opt=Phix(s_end);
            fprintf('Chemin optimal trouvé; d_opt=%g\n',d_opt);
            break;
        end
        % On boucle sur les successeurs s_succ de s_current
         
        for i=1:numel(G.succ{s_current})
            s_succ=G.succ{s_current}(i);
            lx = norm(G.xy(s_succ,:)-G.xy(s_end,:));
          % si s_succ n'est ni dans S ni dans Sc
          %. . .
          if Openlist(s_succ)==0 && Closelist(s_succ)==0;
             Openlist(s_succ)=1;
             Fx(s_succ)=Fx(s_current)+G.c{s_current}(i);
             Phix(s_succ) = Fx(s_succ)+lx;
             pred(s_succ)=s_current;
             
             % sinon si la nouvelle distance est < à la précédente
          elseif Fx(s_current)+G.c{s_current}(i)+lx < Phix(s_succ)
             Fx(s_succ)=Fx(s_current)+G.c{s_current}(i); 
             Phix(s_succ) = Fx(s_succ)+lx   
             pred(s_succ)=s_current;
             
             if Closelist(s_succ)==1 
                 Closelist(s_succ)=0;
                 Openlist(s_succ)=1;
             end
          
          end
        end
    end
    
    % Construction du chemin solution à partir du vecteur pred
   
    fin=false;
    s=s_end;
    c_opt=s_end;
    while ~fin
        s = pred(s);
        c_opt = [c_opt s];
        if s==s_start, fin=true; end; 
    end

    c_opt=c_opt(end:-1:1);

end
