Répondre à la discussion
Affichage des résultats 1 à 14 sur 14

Graphe: plus long chemin



  1. #1
    oli1978

    Graphe: plus long chemin


    ------

    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

    -----

  2. Publicité
  3. #2
    matthias

    Re : Graphe: plus long chemin

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

  4. #3
    enderalartic

    Re : Graphe: plus long chemin

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

  5. #4
    oli1978

    Re : Graphe: plus long chemin

    Citation Envoyé par 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.
    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.

  6. #5
    matthias

    Re : Graphe: plus long chemin

    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.

  7. A voir en vidéo sur Futura
  8. #6
    oli1978

    Re : Graphe: plus long chemin

    Citation Envoyé par 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.

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

  9. Publicité
  10. #7
    matthias

    Re : Graphe: plus long chemin

    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.

  11. #8
    enderalartic

    Re : Graphe: plus long chemin

    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 ..

  12. #9
    matthias

    Re : Graphe: plus long chemin

    Citation Envoyé par 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 ..
    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.

  13. #10
    C.B.

    Re : Graphe: plus long chemin

    Citation Envoyé par 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
    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.

  14. #11
    enderalartic

    Re : Graphe: plus long chemin

    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.

  15. #12
    matthias

    Re : Graphe: plus long chemin

    Citation Envoyé par enderalartic
    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.

  16. Publicité
  17. #13
    oli1978

    Re : Graphe: plus long chemin

    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).

  18. #14
    DDlacombine

    Re : Graphe: plus long chemin

    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.

Sur le même thème :

Discussions similaires

  1. Géodésique, le plus court ou le plus long chemin ?
    Par benjy_star dans le forum Physique
    Réponses: 11
    Dernier message: 19/04/2007, 00h44
  2. chemin dans un graphe
    Par ranell dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 02/03/2007, 21h33
  3. intégrale le long d'un chemin
    Par anais_h dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 20/02/2007, 01h58
  4. chemin elementaire le plus long
    Par sahdow dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 23/10/2006, 11h34
  5. graphe
    Par sahdow dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 02/06/2006, 11h37