Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



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

algorithme de Warshall (théorie des graphes)

  1. loulou40

    Date d'inscription
    juillet 2006
    Âge
    29
    Messages
    211

    algorithme de Warshall (théorie des graphes)

    Bonjour à tous,
    J'étudie cet algorithme en ce moment et même si je comprends à peu près l'algo en lui-même, je ne sais pas comment interprêter le résulat qu'il fournit (à savoir, une matrice si je ne me trompe pas)
    Si quelqu'un a déjà vu cet algo et sait à quoi il sert concrètement, merci de m'éclairer


     


    • Publicité



  2. acx01b

    Date d'inscription
    avril 2004
    Localisation
    paris
    Messages
    2 088

    Re : algorithme de Warshall (théorie des graphes)

    salut apparement il permet simplement de savoir s'il existe un chemin de i à j
    et par extension l'algorithme de floyd warshall permet de connaître la valeur du plus court chemin de i à j

    l'intéret est simplement de constater que si le plus court chemin de i à j se calcule en O(n²), le plus court chemin de i à j pour tout i,j se calcule en O(n^3) et non pas en O(n^4)

    la méthode basique en O(n^4) consiste en:
    pour tout i,j calculer le plus court chemin de i à j avec un algo en O(n²)
     

  3. damboy

    Date d'inscription
    octobre 2008
    Âge
    29
    Messages
    78

    Re : algorithme de Warshall (théorie des graphes)

    Serait-ce une version améliorée de l'algorithme de Dijkstra ?

    http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
     

  4. acx01b

    Date d'inscription
    avril 2004
    Localisation
    paris
    Messages
    2 088

    Re : algorithme de Warshall (théorie des graphes)

    O(n^3) ce n'est pas une amélioration de O(n²)

    dijkstra calcule le plus court chemin entre i et j
    (floyd) warshall le plus court (l'existence d'un) chemin entre i et j pour tout sommet i et j
     

  5. loulou40

    Date d'inscription
    juillet 2006
    Âge
    29
    Messages
    211

    Re : algorithme de Warshall (théorie des graphes)

    Merci pour vos solutions
    Je m'aperçois que je ne comprends pas vraiment la solution de l'algorithme : on part de la matrice d'incidence qu'on modifie puis on fait des opérations sur la matrice de sorte qu'elle ne soit plus composée que de 0 et 1 et à la fin, on a surtout des 1. Peut-on interpréter cette matrice comme donnant tous les chemins possibles entre i et j (défini par les 1 de la matrice finale)?
     


    • Publicité



  6. acx01b

    Date d'inscription
    avril 2004
    Localisation
    paris
    Messages
    2 088

    Re : algorithme de Warshall (théorie des graphes)

    oui et non
    il y a un 1 dans cette matrice s'il existe un chemin entre i et j (regarde sur wikipedia c'est bien expliqué)

    donc on sait que s'il existe un chemin entre i et k, et un chemin entre k et j, alors il existe un chemin entre i et j qui passe par k, mais qui peut très bien passer 2 fois au même endroit

    (par exemple on va de i à m, puis de m à k, puis on rebrousse chemin de k à m, puis on va de m à j --> peut-on dire qu'il y a un chemin de i à j qui passe par k ?)
     

  7. loulou40

    Date d'inscription
    juillet 2006
    Âge
    29
    Messages
    211

    Re : algorithme de Warshall (théorie des graphes)

    Citation Envoyé par acx01b Voir le message
    oui et non
    il y a un 1 dans cette matrice s'il existe un chemin entre i et j (regarde sur wikipedia c'est bien expliqué)

    donc on sait que s'il existe un chemin entre i et k, et un chemin entre k et j, alors il existe un chemin entre i et j qui passe par k, mais qui peut très bien passer 2 fois au même endroit

    (par exemple on va de i à m, puis de m à k, puis on rebrousse chemin de k à m, puis on va de m à j --> peut-on dire qu'il y a un chemin de i à j qui passe par k ?)
    je pense que c'est l'algo de (warshall) floyd et pas de warshall...ceci dit, (warshall) floyd utilise warshall...
    j'ai regardé l'explication de Wikipedia mais je ne comprend toujours pas le rapport entre ce qui semble être le but de cet algo : trouver les chemins entre tous les sommets et cette matrice qu'on obtient à la fin de l'algo puisqu'on peut dire de cette matrice : s'il existe un chemin entre i et m et m et k, ça veut dire qu'il existe une chaîne entre i et k (pas forcément un chemin).
     


    • Publicité




Poursuivez votre recherche :




Sur le même thème :




 

Discussions similaires

  1. théorie des graphes, énigme
    Par christophe_de_Berlin dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 21/03/2008, 18h28
  2. Théorie des graphes
    Par NAGHAM dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 01/01/2008, 14h18
  3. Théorie des graphes
    Par -Zweig- dans le forum Lectures scientifiques
    Réponses: 4
    Dernier message: 21/12/2007, 12h05
  4. Theorie des graphes
    Par BioBen dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 29/11/2007, 19h25
  5. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 23h59