Djikstra [Résolu]

Signaler
Messages postés
10
Date d'inscription
lundi 30 décembre 2002
Statut
Membre
Dernière intervention
12 juillet 2005
-
Messages postés
1154
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
-
Bonjour



Je cherche à savoir s'il est possible d'utilisé l'algo de djikstra pour
trouvé le chemin le plus cours en php. Je connais bien l'algo pour
l'avoir implémenté en C. Parcontre en php, sans les pointeur, j'ai du
mal à cibler une solution fiable.



Si c'est possible, merci de "m'orienté" vers la bonne manière! Ou si
vous connaissez un autre algo pour trouver les chemins les plus cours
(autre que bellman-ford car en fait c'est un dérivé de Djikstra)
fesable en php, faites moi le savoir!





Je commence à songé à faire l'algo en C/C++ et de récuperer les
résultats sous format XML... mais du coup ca me limite énormément pour
les hébergeurs..et encore la, faudrait que je vérifie s'il est possible
d'attendre que le thread du programme C/C++ soit terminé pour récuperer
le fichier xml...



Merci beaucoup!

3 réponses

Messages postés
1154
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
15
Hello,

En regardant le pseudocode de la page http://en.wikipedia.org/wiki/Dijkstra's_algorithm, je ne vois pas pourquoi tu as besoin de pointeurs? Avec des Array, ca doit pouvoir se faire sans probleme!

Enjoy, ++
Messages postés
10
Date d'inscription
lundi 30 décembre 2002
Statut
Membre
Dernière intervention
12 juillet 2005

Peut-etre que je pense trop en fonction de mes connaissance de C. Si on
prend une node quelconque, j'ai des pointeurs qui pointe ses voisins
(d'autre node). En php avec des array, je devrai avoir des doublons
pour chaque voisin, c'est-a-dire une liste de voisin indépendante du
node-voisin lui-meme. Au mieu je pourrai garder qu'un numéro de
réference pour éviter la surcharge d'information.



Donc pour chaque voisin, je devrai aller chercher le "vrai" node voisin
pour modifier son état. Et pour chaque voisin du voisin, etc je devrai
repeter le meme traitement.. J'ai peur que ca devient trop lent.
Surtout que j'envisage d'avoir un graphe concidérablement gros. Avec
des pointeur puisque tout les node sont lié ensemble dynamiquement,
c'est un vrai charme..



Parcontre a force d'y penser, j'ai eu l'idée de lié directement chaque
node du graphe a un enregistrement dans une BD et d'utilisé des
procédure stocké pour optimisé un peu le tout.



Enfin j'ai plein d'idée mais je veux m'assuré de prendre la bonne voila
tout... J'ai pas envie de tout recommencer apres X heures de travail
car je me rend compte que c'est trop lent..
Messages postés
1154
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
15
j'implémente de temps en temps des algo en php pour le plaisir (je me soigne pourtant )
et je peux te dire une chose: tu veux pas être lent et faire de l'algo,
alors fais en C, sinon, bah, ben t'es lent pis c'est pas la mort .



L'usage d'une BD est une bonne idée selon moi, ca remplace les
pointeurs, hehe... je serai intéressé par le résultat si jamais...



Bon courage, enjoy ++