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

---

Commentaire sur cette source (11)
Ajouter un commentaire et/ou une note

L'algorithme de Dijkstra est aussi appelé algorithme de recherche du plus court chemin, il permet donc de trouver le chemin de poids minimal dans un graphe depuis un sommet de départ.

Vous trouverez une description du fonctionnement de l’algorithme de Dijkstra sur wikipédia : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Je me suis aidé de la version écrite en C par Sniper_Fou disponible ici : http://www.cppfrance.com/code.aspx?ID=29352, j’ai donc porté sa version en JavaScript.
J’ai utilisé cet algorithme dans mon projet perso de visite virtuelle : MyFlashPano (version JavaScript) disponible sur mon site perso.

Au passage j'ai testé ma source avec IE6, Firefox 1.5, Opera 9 et Netscape 7.1, le seul petit problème rencontré vient de la gestion des CSS de IE (la position du rond vert est incorrecte). Donc si vous voyez mon erreur, ça m'intéresse...

Vous trouverez dans le zip toutes les sources ainsi que les fichiers xml d'exemple.

/********************************************************** 
 *	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
}

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

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.

• DOM BUILDER : PROTOTYPE ROCKS !
• CLASSE AJAX : PROTOTYPE ROCKS !
• AFFICHAGE DE PANORAMA 360° (JAVASCRIPT ORIENTÉ OBJET) - YAJEVLE
• MYFLASHPANO VERSION JAVASCRIPT - UN SYSTÈME DE VISITE VIRTUELLE : PANORAMA 360° + VIDÉO + CARTE (LE TOUT CONFIGURÉ PAR XML)

• BOITE DE DIALOGUE (AVEC GRISEMENT DE LA PAGE)
• GADGET RTL2
• CLASS.JS , TEST D'IMPLÉMENTATION DE CLASS EN JAVASCRIPT
• GETCOMPUTEDSTYLE POUR IE (GETCOMPUTEDCSSVALUE) [PT TO PX, EM TO PX, CM TO PX, ...]
• POCKET PC - WIMO

• RECHERCHE ET COLORISATION, MISE EN SURBRILLANCE
• MOTEUR DE RECHERCHE GOOGLE SUR SON SITE EN DEUX MINUTES - RÉSULTATS À L'INTÉRIEUR DE SON SITE
• D.SEARCH :: MOTEUR DE RECHERCHE QVDLM
• RECHERCHE AVEC AUTOCOMPLETION AJAX ( AVEC NAVIGATION CLAVIER ET SOURIS )
• RECHERCHE ET SURBRILLANCE