RECHERCHE DU PLUS COURT CHEMIN - ALGO DE DIJKSTRA - EN JAVASCRIPT

/********************************************************** 
 *	Module Javascript : Algo de Dijkstra              *
 *      (Recherche du plus court chemin)                  *
 *	- Développé par Henri ASTRE                       *
 *	- Site Web : http://astre.henri.free.fr           *
 *	                                                  *
 *	Algo de Dijkstra porté en JavaScript depuis       *
 *  la version en C de Sniper_Fou disponible              *
 *  ici : http://www.cppfrance.com/code.aspx?ID=29352     *
 **********************************************************/
 
 
/* Les variables globales */ 
var DISTANCE_MAX = 999999999; // equivalent de FLT_MAX
	
//Fonction d'initialisation de l'algo de Dijkstra 
function Init_Dijkstra(numSelectionne)
{
    var pcc_distance        = new Array(nbPano); //tableau de distance, (nbPano = nombre de sommet)
    var pcc_predecesseur    = new Array(nbPano); //tableau de predecesseur
    var pcc_est_deja_traite = new Array(nbPano); //tableau des sommets déja traités
	
    var Dep = numSource;      //numéro du pano de départ
    var Arr = numSelectionne; //numéro du pano d'arrivée
    
    //initialise chaque distance à l'infini et aucun predecesseur pour chaque pano
    for(var i=0; i<nbPano; i++)
    {
        pcc_distance[i]         = DISTANCE_MAX; //distance infinie
        pcc_est_deja_traite[i]  = 0;
    }
        
    pcc_distance[Dep]        = 0  //distance du départ à lui meme 0
    pcc_est_deja_traite[Dep] = 1; //le sommet de départ est traité
        
    //lance l'itération de l'algo
    Iter_Dijkstra(Dep, 1, pcc_distance, pcc_predecesseur, pcc_est_deja_traite);
    
    Affiche_Parcours_Min(Dep, Arr, pcc_distance, pcc_predecesseur);
}

//Fonction qui détermine chaque itération de l'algorithme de Dijkstra
function Iter_Dijkstra(pcc_num_courant, nb_deja_traites, pcc_distance, pcc_predecesseur, pcc_est_deja_traite)
{
    //parcour de la liste des successeurs
    for(var i=0; i<graphe_list[pcc_num_courant].length; i++)
    {
        //calcule la distance la plus courte de chaque sommet
	var num_voisin    = graphe_list[pcc_num_courant][i][0];
	var dis_voisin    = graphe_list[pcc_num_courant][i][1];
	var id_voisin     = graphe_list[pcc_num_courant][i][2];
	var ancienne_dist = pcc_distance[num_voisin];
        
        //calcule la plus courte distance
        pcc_distance[num_voisin] = Math.min(pcc_distance[num_voisin], pcc_distance[pcc_num_courant] + dis_voisin);
        
         //si on a modification de la distance minimale alors on a changement de prédécesseur
        if(ancienne_dist != pcc_distance[num_voisin])
        {
            pcc_predecesseur[num_voisin] = new Array(pcc_num_courant,id_voisin); // modif pour stocker id ...
        }
    }

    var nouveau_sommet = -1;       //nouveau sommet à étudier
    var min_sommet = DISTANCE_MAX; //distance du sommet successeur le plus proche
    
    //recherche le sommet suivant qui est le sommet de distance minimale non traité par dijkstra
    for(i=0; i<nbPano; i++)
    {
        if(pcc_est_deja_traite[i] == 0)
        {
	    //choisis la distance du successeur le plus proche
            min_sommet = Math.min(min_sommet, pcc_distance[i]);  
            
            //choisis le successeur le plus proche
            if(min_sommet == pcc_distance[i])                    
                nouveau_sommet = i;
        }
    }    
    
    //ce nouveau sommet est considéré comme traité
    pcc_est_deja_traite[nouveau_sommet] = 1;
    nb_deja_traites++;
        
    //relance la récursive tant que tous les sommets non pas été traités
    if(nb_deja_traites != nbPano)
        Iter_Dijkstra(nouveau_sommet, nb_deja_traites, pcc_distance, pcc_predecesseur, pcc_est_deja_traite);
}

//affichage du plus court chemin
function Affiche_Parcours_Min(Dep, Arr, pcc_distance, pcc_predecesseur)
{
    var parcours = Arr;
    var tmp = 0;
    var trajet = new Array();
    
    //si il n'y a pas de trajet possible
    if(pcc_distance[Arr] == DISTANCE_MAX)
        alert('Il n\'y a pas de trajet !');
     
    else
    {
	var chaine = 'PCC : ';
    
        //tant qu'on est pas revenu au point de départ
        while(parcours != Dep)
        {
            var tmp_id = pcc_predecesseur[parcours][1];
            parcours   = pcc_predecesseur[parcours][0];

            var list = new Array(parcours, tmp_id);
            trajet.push(list);  
        }
        
        //pour que le trajet soit dans le bon ordre : Dep -> Arr
	trajet.reverse();
		
	for(var i=0; i<trajet.length; i++)
	{
		chaine += 'pano_'+parseInt(trajet[i][0])+' -> ';
	}

	var max = trajet.length-1;
	chaine += 'pano_'+Arr;
	alert(chaine);
    }    
    
    loadpano(Arr); //déplace le point vert qui indique la position courante
}

Télécharger le zip

16 juillet 2006 11:03:22 :

Ajout du zip et du screenshot

16 juillet 2006 11:11:56 :

Ajout du fichier zip avec un exemple complet.

16 juillet 2006 11:29:36 :

Ajout du screenshot

16 juillet 2006 11:39:30 :

Ajout du fichier zip avec un exemple complet.