Graphe: plus long chemin

[oli1978]

Bonjour,

Existe-t-il un algorithme de recherche du plus long chemin dans un graphe non-orienté, valué et acyclique ?
Sinon, est-il possible d'adapter un des algorithmes de calcul du plus court chemin pour résoudre le problème ?

Merci d'avance
-----

[matthias]

Tes points d'arrivée de départ sont fixés ?
Si c'est le cas je ne vois pas vraiment le problème.

[enderalartic]

d'autant que non orienté et acylique ca doit foncer ..

[oli1978]

Tes points d'arrivée de départ sont fixés ?
Si c'est le cas je ne vois pas vraiment le problème.

Non. Je cherche en fait tous les plus longs chemins dans un graphe. Ni les points de depart, ni les point d'arrivee ne sont connus.

[A voir en vidéo sur Futura]

[matthias]

On peut imaginer pas mal d'algorithmes.
Déjà, tu peux réduire ton graphe en considérant toutes les parties linéaires comme une seule arête dont la valuation est la somme des valuations des arêtes la composant (j'espère que toutes tes valuations sont positives).
Ensuite, part d'un sommet terminal (une seule arête adjacente). Tu arrives à un noeud. Tu examines tous les sommets terminaux liés à ce noeud et tu ne gardes que celui qui est relié par une arête de valuation maximale. Tu fais ça en boucle sur tous les sommets terminaux jusqu'à obtenir un graphe composé de deux sommets liés par une arête. Ce graphe te donne un chemin maximal.

Bon c'est juste une proposition, on peut sans doute faire mieux.

[oli1978]

On peut imaginer pas mal d'algorithmes.
Déjà, tu peux réduire ton graphe en considérant toutes les parties linéaires comme une seule arête dont la valuation est la somme des valuations des arêtes la composant (j'espère que toutes tes valuations sont positives).
Ensuite, part d'un sommet terminal (une seule arête adjacente). Tu arrives à un noeud. Tu examines tous les sommets terminaux liés à ce noeud et tu ne gardes que celui qui est relié par une arête de valuation maximale. Tu fais ça en boucle sur tous les sommets terminaux jusqu'à obtenir un graphe composé de deux sommets liés par une arête. Ce graphe te donne un chemin maximal.

Bon c'est juste une proposition, on peut sans doute faire mieux.

En tous cas, un grand merci. Ca me met sur une piste interessante, je vais creuser un peu a partir de la.

[matthias]

Bon je viens de pondre ça comme ça, cette méthode m'a l'air assez naturelle. Si tu avais un exemple de graphe, on pourrait voir ce que ça donne. Il faut aussi la fignoler un peu pour trouver tous les chemins et pas uniquement un.

[enderalartic]

Marche pas ton truc mat , tu gardes qu' un chemin si tu en as deux de meme valeur mais l'idee est la quand meme je pense, mais comme dit mat si tu as une valeur negative tout est foutu , en fait non je dis une connerie , tu ne peux pas avoir de valeur positive dans ton graphe soit le graphe fait dun segement ab valué 1 abababab ..

[matthias]

Marche pas ton truc mat , tu gardes qu' un chemin si tu en as deux de meme valeur mais l'idee est la quand meme je pense, mais comme dit mat si tu as une valeur negative tout est foutu , en fait non je dis une connerie , tu ne peux pas avoir de valeur positive dans ton graphe soit le graphe fait dun segement ab valué 1 abababab ..

J'ai pas tout compris ...
Est-ce que les valuations peuvent être négatives ou pas ?
Sinon, le fait de ne garder qu'un seul chemin, n'est pas vraiment un problème, c'était surtout pour expliquer ma méthode. Tu peux faire une boucle sur toutes les arêtes de valuation max, n'en garder qu'une à la fois et continuer l'algo dans chacun des cas. Ca doit même pouvoir se programmer de manière récursive.

[C.B.]

Bonjour,

Existe-t-il un algorithme de recherche du plus long chemin dans un graphe non-orienté, valué et acyclique ?
Sinon, est-il possible d'adapter un des algorithmes de calcul du plus court chemin pour résoudre le problème ?

Merci d'avance

Si le graphe est fini et acyclique le nombre de chemin possible est fini. Il suffit de les énumérer tous.
La recherche du plus long chemin dans un graphe non-orienté valué et acyclique est donc Turing-Calculable (que le graphe soit représenté par une matrice, sa fonction de transition ou autre).
Il est même possible de rechercher dans un graphe valué quelconque le plus long chemin sans boucle (le nombre de possibilité est encore fini)

Je ne me souviens plus de la complexité du problème par contre.

[enderalartic]

Je voulais dire que si trois noeuds a b c sont reliés cela fait un cycle c'est meme la definition je crois (mes souvenirs d'algo des graphes ont 2 ans mais je les ais rafraichis du coup) mais dans un graphe non orienté, qu'est ce qui t'empeche de faire a->b b->a a->b ..., dommage, je n'ai plus de prof sous la main, c'est ce que je voulais dire, et donc avec des valeurs positive il aurait été impossible de trouver le plus long chemin, voila il doit y avoir une contrainte qui dit qu il est impossible de revenir sur ses pas.

[matthias]

voila il doit y avoir une contrainte qui dit qu il est impossible de revenir sur ses pas.

Oui je pense que c'est sous-entendu, sinon il n'y a clairement pas de solution.

[oli1978]

Merci a vous, je vais voir ce que je peux faire avec ca. Je voulais ismplement eviter une exploration complete. En rajoutant qques contraintes, je devrais cependant y arriver.
Pour repondre a vos uqestions, il n'y a pas de valuations negatives, les allers-retours sont interdits.
Par ailleurs, j'ai des sommets d'ordre 1, et des sommets d'ordre quelconque (generalement 2).

[invite69b7411e]

Pour trouver le plus long chemin ? Facile, prends un taxi !


Sinon:
http://dept-info.labri.fr/~dicky/ENSEIGNEMENT/GA-CNAM/
Les p.32 et suivantes du pdf peuvent peut-être t'inspirer.