Discussion :

[CliffeCSTL]

Bonjour,

Je cherche un algo rapide pour trouver un chemin dans un graphe de poids maximal. Voici à quoi ressemble mes graphes :

L'idée est de partir du point a vers le point b sachant qu'on ne peut passer que par n <= 2 (m p) + 1 arcs (sur mon exemple p = 3), ou encore par au plus (m p) arcs horizontal. Tous les arcs ou je n'est rien noté ont un poids nul.


Le graphe, pour faire simple : chaque sommet de gauche est relier à un sommet à droite et à un poids. Un sommet de droite est relié (ou non) à tous les sommets d'un groupe situer en dessous.


Merci.

[Trademark]

Salut,

Il n'existe pas d'algorithme rapide qui fasse ça dans un graphe car c'est un problème NP-complet (http://en.wikipedia.org/wiki/Longest_path_problem).

Sauf que dans ton cas on dirait que ton graphe est en fait un arbre (plus précisément un DAG) vu qu'il n'y a pas de cycle. Ce qui fait que ton problème n'est pas NP-Complet et peut être résolu en temps linéaire (youpi).

Par conséquent un algorithme pour le plus court chemin :

* Effectue un tri topologique sur ton DAG : http://fr.wikipedia.org/wiki/Tri_topologique (voir version en. pour algo). O(V + E).
* Relâche chaque arête (u, v) dans cette ordre, et calcule le poids minimum pour atteindre v (tu gardes une table des coûts (noeud, distance) comme dans Dijsktra). Vu que c'est trié dans l'ordre topologique, tu seras sûre que u a déjà été calculé.
* Le résultat final se trouve dans distance[b].


Pour le plus long chemin, une astuce est de faire (poids * -1) et d'utiliser le même algo que précédement. Tu feras *-1 le résultat final.

Voilà, c'est peut-être pas hyper bien expliqué mais tu sais où chercher

[CliffeCSTL]

Merci. Je vais voir tous ça.
Par contre, est-ce que cela fonctionne dans le cas d'un multi graphe ? (plusieurs arcs horizontal ?)

[Trademark]

Oui tant que ça n'introduit pas de cycle, tu dois juste veiller à ce que ton graphe reste un DAG.