// TP 4 : algorithme de Dijkstra

clear

// POUR RAPPEL :
// Un graphe oriente est defini par 
//     - ses sommets (numerotes de 1 a Ng)
//     - la donnee de ses arcs (tableaux de type 'arc_*')
//     - la donnee de la valuation de chaque arc (tableaux de type 'val_*')

// Le format choisi ici est celui de la matrice d'adjacence et de la matrice de
// valuation correspondante (voir TP 1)


function [d,P]=Dijkstra(M,f)

// ENTREE :
//    - M : matrice d'adjacence
//    - f : matrice de valuation
// VARIABLES INTERMEDIAIRES :
//    - N : nombre de sommets du graphe
//    - Z : vecteur des sommets marques 
//	    Z(i)=1 si i est marque 
//      Z(i)=0 si i est non marque
// SORTIE :
//    - d : vecteur des distances du sommet 1 aux autres sommets
//    - P : vecteurs des predecesseurs des sommets

N=size(M,1);
Z=zeros(1,N);

// I. INITIALISATION

Z(1)=1;
d(1)=0;
P(1)=%inf;

for i=2:N
    if (M(1,i)==1) then
        d(i)=f(1,i);
        P(i)=1;
    else
        d(i)=1e+6;
        P(i)=%inf;
    end
end

// II. BOUCLE DE MISE A JOUR DES DISTANCES ET PREDECESSEURS

while (sum(Z)<N)
    
    // II.1. DETERMINER LA LISTE DES SOMMETS NON MARQUES Lnm 
    //       ET LA LISTE DES DISTANCES COURANTES Dnm
    Lnm = [];
    Dnm = [];
    for i=1:N
        if (Z(i) == 0) then 
            Lnm = [Lnm i];
            Dnm = [Dnm i];
        end
     end

    // II.2. IDENTIFIER UN SOMMET 'x' POSSEDANT LA DISTANCE MINIMALE
    //       PARMI LES SOMMETS NON MARQUES. "MARQUER" CE SOMMET 'x'
    // Rem. : si Vec est un vecteur ligne, l'instruction '[vmin,pos]=min(Vec)'
    //        renvoit la valeur minimale du vecteur (vmin) et la position dans 
    //        le vecteur de cette valeur minmale (pos)

    [Dmin,pos] = min(Dnm);
    x = Lnm(pos);
    Z(x) = 1;




    // II.3. EN PARCOURANT LES SOMMETS DU GRAPHE, IDENTIFIER LES
    //       SUCCESSEURS NON MARQUES DE 'x' ET METTRE A JOUR,
    //       EVENTUELLEMENT, LEUR DISTANCE ET PREDECESSEUR
    for i=1:N
        if (Z(i)==0) & (M(i,x) == 1) then
            if (d(i) > (d(x)+f(i,x))) then
                d(i) = d(x)+f(i,x);
                P(i) = x;
            end
        end
    end
end
endfunction

// EXEMPLES DU COURS :
// Test de l'algorithme avec un graphe possedant des valuations positives
arc_Mg=[0,1,1,1;0,0,0,0;0,1,0,0;0,1,1,0];
val_Mg=[%inf,8,6,2; %inf,%inf,%inf,%inf; %inf,3,%inf,%inf; %inf,5,1,%inf];

[d,P]=Dijkstra(arc_Mg,val_Mg)

// On devrait obtenir
// d=[0.   6.   3.   2.]
// P=[Inf   3.   4.   1.]

// Test de l'algorithme avec un graphe possedant une valuation negative
// (mise en echec de l'algorithme de Dijkstra)
arc_Mg=[0,1,1;0,0,0;0,1,0];
val_Mg=[%inf,3,4; %inf,%inf,%inf; %inf,-2,%inf];

[d,P]=Dijkstra(arc_Mg,val_Mg)
// On devrait obtenir
// d=[0.   3.   4.]
// P=[Inf   1.   1.]
