Djikstra

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!

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..

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 ++