Gros pépin en php pour algorithme de Dijkstra.

Signaler
Messages postés
32
Date d'inscription
lundi 24 janvier 2011
Statut
Membre
Dernière intervention
26 octobre 2011
-
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
-
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

Messages postés
60
Date d'inscription
jeudi 10 mars 2005
Statut
Membre
Dernière intervention
26 octobre 2011

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:)
Messages postés
32
Date d'inscription
lundi 24 janvier 2011
Statut
Membre
Dernière intervention
26 octobre 2011

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.
Messages postés
60
Date d'inscription
jeudi 10 mars 2005
Statut
Membre
Dernière intervention
26 octobre 2011

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.
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
42
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