begin process at 2008 08 28 21:45:46
1 233 393 membres
485 nouveaux aujourd'hui
14 291 membres club

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

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


Information sur la source

Catégorie :Divers Classé sous : recherche, plus, court, chemin, myflashpano Niveau : Initié Date de création : 15/07/2006 Date de mise à jour : 16/07/2006 11:39:30 Vu / téléchargé: 10 374 / 34 817

Note :
10 / 10 - par 3 personnes
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

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

Description

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.

Source

  • /**********************************************************
  • * 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
  • }
/********************************************************** 
 *	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.
  • signaler à un administrateur
    Commentaire de rrk275 le 16/07/2006 02:03:10

    ca manque d'un moyen de tester ..

  • signaler à un administrateur
    Commentaire de ralecul le 16/07/2006 11:13:31

    Effectivement mon fichier zip et mon screenshot n'ont pas été uploadés... C'est quoi cette discrimination pour les bas débits :-)
    J'ai droit a une méchante Erreur http 500 à chaque fois...
    Mon fichier zip contient effectivement un moyen de tester, mais pour l'instant je ne vois pas comment faire pour l'envoyer, peut-être lundi pendant mon stage... Je suis vraiment désolé !

  • signaler à un administrateur
    Commentaire de rrk275 le 16/07/2006 11:41:48

    Salut,
    perso j'ai le screen et pas le zip ..l'algo a l'air bon, mais si tu intergres ca à une grosse appli c'est dommage les variables globales ...

  • signaler à un administrateur
    Commentaire de rrk275 le 16/07/2006 11:42:15

    maintenant j'ai le zip ^^

  • signaler à un administrateur
    Commentaire de rrk275 le 16/07/2006 11:48:06

    bah l'algo a l'air correct ( faudrait faire quelque tests ..) maintenant je suis tellement bluffé par la map en xml et le graphe aussi que je met 10/10 ..

  • signaler à un administrateur
    Commentaire de ralecul le 16/07/2006 12:13:26

    Merci RRK275 !

    J'ai effectivement réussi à rajouter le zip et le screenshot.
    J'ai oublié de préciser que j'ai inclus un petit guide en pdf pour expliquer le fonctionnement de cette source.
    De plus cette source utilise effectivement un fichier XML pour la définition du graphe, mais si vous voulez voir un code plus intéressant au niveau de la gestion des fichiers XML je vous conseille de jetter un coup d'oeil à mon autre source : MyFlashPano.
    Elle est disponible ici : http://www.javascriptfr.com/codes/MYFLASHPANO-VERSION-JAVASCRIPT-SYSTEME-VISITE-VIRTUELLE-PANORAMA-360_38341.aspx

  • signaler à un administrateur
    Commentaire de rrk275 le 16/07/2006 21:58:00

    Comment s'appelle cette bougarde qui m'a l'air bien sympathique?

  • signaler à un administrateur
    Commentaire de ralecul le 17/07/2006 09:20:10

    @RRK275 :
    Cette bourgade s'appelle ALLONS, c'est un petit village de moins de 200 âmes pour un peu plus de 7700ha. C'est donc un joli désert avec moins de 2hab/km² et surtout un réseau téléphonique assez précaire... C'est sans doute à cause de celà que j'ai eu des ennuis pour poster cette source au début...

    @all:
    Pour ceux qui ne voit pas de quoi on parle, vous pouvez jetter un coup d'oeil à la demo javascript de MyFlashpano : http://astre.henri.free.fr/myflashpano-demo-javascript.php. (ou peut-être que RRK275 ne parle que de la carte de cette source :-)

  • signaler à un administrateur
    Commentaire de chapodepay le 18/04/2007 21:25:51

    pano.js
    ligne 95,
    return document.allid;
    remplacer par
    return document.all[id];

  • signaler à un administrateur
    Commentaire de twin le 12/11/2007 22:21:12

    Magnifique source !
    Toutes mes felicitations : c'est bien fait, clair, tout est facile à comprendre (dans le code, mon cerveaux est toujours sous le choc de l'algorithme !).
    Le PDF et wikipedia sont quand meme de grande utilité.

    Merci pour ce code.
    Il m'a donné envie de me mettre à l'adapter : faire un algorithme de recherche de sortie d'un labyrinthe.
    Du travail m'attends !!!

  • signaler à un administrateur
    Commentaire de twin le 12/11/2007 23:06:22

    Un labyrinthe, oui, mais en fait c'est interessant qui si il y a plusieurs chemins possibles, donc recherche du chemin le plus court parmis tout ceux existants!

Ajouter un commentaire

Pub



Appels d'offres

Recherche developpeur ...
Budget : 700€
SITE MARCHAND LOCATION...
Budget : 3 000€
SITE MARCHAND POUR HOTEL
Budget : 4 000€

CalendriCode

Août 2008
LMMJVSD
    123
45678910
11121314151617
18192021222324
25262728293031

Téléchargements

Logiciels à télécharger sur le même thème :

Boutique

Boutique de goodies CodeS-SourceS