|
Trouver une ressource
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
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
}
Fichier Zip
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
Historique
- 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.
Sources du même auteur
Sources de la même categorie
Sources en rapport avec celle ci
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Rechercher dans un fichier texte [ par gg16819 ]
BonjourJe souhaiterais faire un petit moteur de recherche en javascript. Pour cela, je dois pouvoir ouvrir des fichiers externes (html et texte) et pa
Recherche script javascript pour menu deroulant [ par devess ]
Bonjour,J'ai cherché mais je n'ai pas trouvé de script javascript pour faire des menus déroulants avec un affichage d'une fenêtre lors du passage curs
Recherche script javascript pour menu deroulant [ par devess ]
Bonjour,J'ai cherché mais je n'ai pas trouvé de script javascript pour faire des menus déroulants avec un affichage d'une fenêtre lors du passage curs
HELP - RECHARGER LES FRAMES - HELP [ par Yeltaz ]
Bonjour,Je recherche un script qui permette de recharger les frames d'un site lorsque l'on arrive sur une page par l'intermédiaire d'un moteur de rech
recherche javascript fenetre flottante bas droit [ par redbrain ]
bjr, je cherche un javascript qui permette de mettre dans une page html, une fenetre dans un coin en bas et a droite (ou s'affiche une autre page ht
script d'ouverture [ par pronovost ]
Bonjour.Je suis en charge de faire la page Intranet de ma compagnie. Sur celle-ci j'ai un engin de recherche qui parcours les archives de la compagnie
Recherche dans un tableau js [ par dridri ]
Bonjour,Voila j'ai une question qui m'embète pas mal. Je voudrais savoir s'il était possible de faire une recherche dans un tableau js contenant des d
Recherche d'un créateur de banniere [ par Xtaz67 ]
Salut, je ebute en webmaster et la je cree mon site qui est sur un jeu.j'ai un peu de mal a le decorer.Ca serai sympa si une personne qui arrive bien
Recuperer le chemin d'un dossier [ par fab30 ]
Salut, je voudrais pouvoir créer une boite de dialogue identique a <input type="file"> mais pas pour récuper un fichier mais pour récupérer un c
recherche aide [ par g2m ]
nouveau dans la création de site, je bute sur une chose simple, créer un menu déroulant horizontale avec survol.Un truc simple quoi!Dans cette barre 8
|
Téléchargements
Logiciels à télécharger sur le même thème :
Comparez les prix Nouvelle version
|