Gros pépin en php pour algorithme de Dijkstra.

jeffreynaz Messages postés 32 Date d'inscription lundi 24 janvier 2011 Statut Membre Dernière intervention 26 octobre 2011 - 26 oct. 2011 à 10:52
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 - 26 oct. 2011 à 17:13
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.

4 réponses

cs_nemo_1 Messages postés 60 Date d'inscription jeudi 10 mars 2005 Statut Membre Dernière intervention 26 octobre 2011
26 oct. 2011 à 11:20
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:)
0
jeffreynaz Messages postés 32 Date d'inscription lundi 24 janvier 2011 Statut Membre Dernière intervention 26 octobre 2011
26 oct. 2011 à 11:40
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.
0
cs_nemo_1 Messages postés 60 Date d'inscription jeudi 10 mars 2005 Statut Membre Dernière intervention 26 octobre 2011
26 oct. 2011 à 13:41
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.
0
coucou747 Messages postés 12303 Date d'inscription mardi 10 février 2004 Statut Membre Dernière intervention 30 juillet 2012 43
26 oct. 2011 à 17:13
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
0