Gros pépin en php pour algorithme de Dijkstra.

Question

Bonjour j'ai un problème et je galère depuis hier (j'ai le caisson qui fume)

alors voila 

on me demande d'optimiser un trajet selon des secteurs en utilisant un algorithme de Dijkstra.
une personne doit parcourir les différents secteurs pour récupérer des produits.
il le fait par ordre alphabétique mais je dois changer l'ordre de la liste de commande de façon à optimiser son trajet.

j'ai représenté tous mes sommets sur un graphique j'ai 34 sommets, ainsi que les distance entre chaque sommet.

je souhaite représenter ce graphique sous forme de tableau afin de calculer la distance parcourue lorsqu'il va chercher les produit par ordre alphabétique et une autre fois quand l'ordre est optimisé.

je ne vois pas comment faire cela.
avez vous déjà fait cet algo de Dijkstra en php si oui comment ?


répondez moi vite.
Les anti dépresseurs ne font plus effet.

cs_nemo_1 · Answer

Chalute,

20s de recherche google plutard ...:

http://www.codeguru.com/forum/showthread.php?t=430962

http://www.phpclasses.org/browse/file/26469.html

Au moins tu auras des pistes.

Après si tu as un bug dans un code ou autre, je pourrai t'aider...

Bon courage:)

jeffreynaz · Answer

Je sais mec j'ai vu ces algo

mais en fait je souhaiterais faire un tableau qui représente mes 34 sommets ainsi que les distances entre les sommets.

cs_nemo_1 · Answer

Ok mec mais quelle différence y'a til entre un algo qui marche peut être pour 100 sommets et un qui marche pour 34?

Si tu as déjà la logique de la programmation c'est cela me semble t il le plus compliqué non?

Si tu as une base avec laquelle demarrée qui je pense est le plus difficile je ne vois pas quoi d'autre je pourrai faire pour toi à ce stade.

Maintenant si tu veux une solution clef en main, je ne peux pas t'aider.

coucou747 · Answer

Bonjour,

Dijkstra ne sert pas à ça :
Dijkstra sert à calculer le plus court chemin entre deux points (en gros, par quels sommets tu dois passer pour aller de A a B) mais en aucun cas, l'ordre pour passer par tout les sommets.

En gros, tu cherches à résoudre le problème du voyageur de commerce, et je te le dis clairement, pour 34 sommets, ça ne devrait pas bien fonctionner... c'est un problème NP complet...

Il existe plein d'heuristiques marrantes, je te laisse lire la documentation sur le sujet.

Cherche voyageur de commerce sur google.

Cordialement,

Maxime

Gros pépin en php pour algorithme de Dijkstra.

4 réponses

Votre réponse

Discussions similaires