Discussion :

[julie383]

Bonjour,

Je recherche de l'aire sur un programme python, car je galère.

Pour faire simple, je dois aller d'un point de début à un point de fin avec un chemin de plus fort poids. Selon les cas, j'ai le choix pour passer au point suivant entre 1 ou 2 possibilités. Ceci est définit dans des dictionnaires du type :
d={1:{2:poids, 3:poids},2:{4:poids}, 3:{6:poids,8:poids}}

Ceci correspond donc à un DAG (directed acyclic graph). Je dois maintenant dans ce DAG le chemin de plus fort poids. J'ai compris qu'il s'agit de programmation dynamique, mais à part ça je comprends pas du tout comment on code ce genre de chose...

Auriez-vous des pistes, des exemples, des sites qui pourraient m'expliquer comment on fait ? Ce programme doit être codé en python.

Merci d'avance pour votre aide !!

[alexdevl]

Bonjour,
Quelle est le contexte ? ceci est dans un cadre scolaire, professionnel, perso ?
Car la réponse peux être différente : L'accent peux-être mis sur l'efficacité ou la pédagogie.

Alex

[julie383]

Bonjour,

Merci pour votre réponse.
Ceci est dans le cadre scolaire.

[alexdevl]

Bonjour,

La piste à laquelle je pense est de faire une analyse récursive de l'arbre formé par les différents chemins et les stocker dans une variable.

Cela veux dire que pour s'attaquer à cela il faut :
1°) Établir l’algorithme

2°) Connaître les notions suivantes en python
- Les listes
- Les tuples
- Les variables globales ou les class
- Les appels récursifs

3°) Faire le programme

[wiztricks]

Juste pour le fun
Un cours du MIT sur la programmation dynamique avec en illustration de la programmation du shortest path en Python. ici
- W

[julie383]

Bonjour,

Justement, mon problème réside dans l'établissement de l'algorithme... Avez-vous quelques pistes ?

[dividee]

Si, avant de considérer un sommet x, tu connaissais déjà les plus longs chemins vers tous les sommets qui précèdent x dans le graphe, ce ne serait pas trop compliqué, n'est-ce pas ? Le problème se réduit dès lors à trouver un ordre de parcours du graphe qui assure cette propriété (que tous le prédécesseurs de x soient visités avant x). Un tel ordre existe-t-il sur un DAG ?