Djikstra

Résolu
PsYk0PaT Messages postés 10 Date d'inscription lundi 30 décembre 2002 Statut Membre Dernière intervention 12 juillet 2005 - 11 juil. 2005 à 22:51
malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 - 12 juil. 2005 à 17:32
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

malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
12 juil. 2005 à 08:27
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, ++
3
PsYk0PaT Messages postés 10 Date d'inscription lundi 30 décembre 2002 Statut Membre Dernière intervention 12 juillet 2005
12 juil. 2005 à 17:29
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..
0
malik7934 Messages postés 1154 Date d'inscription mardi 9 septembre 2003 Statut Membre Dernière intervention 15 août 2009 17
12 juil. 2005 à 17:32
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 ++
0