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 Dijkstra et plus court chemin

  1. Stratov

    Date d'inscription
    septembre 2007
    Localisation
    Clermont-Ferrand
    Âge
    27
    Messages
    78

    Algorithme de Dijkstra et plus court chemin

    Bonjour. Je travaille actuellement, dans le cadre d'un tipe, sur l'algorithme de Dijkstra, qui est censé donné le plus court chemin entre deux sommets d'un graphe.
    Je ne suis pas un As en programmation, mais si j'ai bien compris, le principe de cet algorithme est de calculer la distance minimale de chaque sommet à la source. Ainsi grâce au point d'arrivé on retrouve le chemin le plus court en remontant de prédécesseur en prédécesseur jusqu'à la source.
    Donc j'en déduit que la somme des plus courts chemins est le plus court chemin.

    Mais est-ce vraiment le chemin le plus court?

    Car je crois avoir trouvé un contre exemple.



    J'ai pris le chemin le plus court pour aller au sommet suivant, et on s'aperçoit qu'il y a une intersection de deux arcs. Or un théorème dit que s'il y a a une intersection alors il existe un chemin plus court sans intersection.

    J'aimerais avoir vos avis, et savoir si je pense mal.

    Merci à tous.


     


    • Publicité



  2. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    44
    Messages
    2 523

    Re : Algorithme de Dijkstra et plus court chemin

    Citation Envoyé par Stratov Voir le message
    Donc j'en déduit que la somme des plus courts chemins est le plus court chemin.
    Dis ainsi c'est maladroit car on peut avoir A-B-C est le plus court chemin pour aller de A à C, C-D est le plus court chemin pour aller de C à D mais A-B-C-D n'est pas nécessairement le plus court.
    Par contre, si le chemin le plus court entre A et D est par exemple A-E-F-D alors A-E est le plus court chemin pour aller de A à E, idem pour aller de A à F et aussi entre E et F.
    Citation Envoyé par Stratov Voir le message
    J'ai pris le chemin le plus court pour aller au sommet suivant, et on s'aperçoit qu'il y a une intersection de deux arcs. Or un théorème dit que s'il y a a une intersection alors il existe un chemin plus court sans intersection.
    La seule intersection sur la figure est celle de [DC] et de [AB]. Mais, cette intersection n'est pas un sommet du graphe. Dans ce cas soit le graphe est mal représenté (et il n'y a en fait pas d'intersection) soit le graphe est mal défini et il faut créer un sommet de plus (l'intersection sus-évoquée).
    Ton théorème n'est valide que si deux arêtes ne peuvent s'intersecter qu'en des sommets (ce qui est toujours supposé en fait dans la théorie des graphes à mon avis).
     

  3. Stratov

    Date d'inscription
    septembre 2007
    Localisation
    Clermont-Ferrand
    Âge
    27
    Messages
    78

    Re : Algorithme de Dijkstra et plus court chemin

    Ok donc en fait la réciproque que je supposé n'est pas vrai. Il est vrai que dit comme ça cela paré plus intuitif. Merci pour cet éclaircissement. salut
     

  4. jobherzt

    Date d'inscription
    janvier 2005
    Âge
    31
    Messages
    1 412

    Re : Algorithme de Dijkstra et plus court chemin

    Citation Envoyé par homotopie Voir le message
    Ton théorème n'est valide que si deux arêtes ne peuvent s'intersecter qu'en des sommets (ce qui est toujours supposé en fait dans la théorie des graphes à mon avis).
    Je suis d'accord que le theoreme concerne les intersections qui correspondent a des sommets (puisque "asbtraitement" seuls les relations entre les sommets comptent).

    Un graphe peut ne pas etre "representable" sans que des aretes ne se croisent hors sommet (ce qui dans le cas present n'a aucune importance, c'est une remarque générale).

    Les graphes qui sont isomorphes a un graphe sans croisements de cette sorte sont dit planaire, c'est une propriété qui peut avoir me semble t il des consequences interressantes.
     

  5. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    44
    Messages
    2 523

    Re : Algorithme de Dijkstra et plus court chemin

    Citation Envoyé par jobherzt Voir le message
    Je suis d'accord que le theoreme concerne les intersections qui correspondent a des sommets (puisque "asbtraitement" seuls les relations entre les sommets comptent).

    Un graphe peut ne pas etre "representable" sans que des aretes ne se croisent hors sommet (ce qui dans le cas present n'a aucune importance, c'est une remarque générale).

    Les graphes qui sont isomorphes a un graphe sans croisements de cette sorte sont dit planaire, c'est une propriété qui peut avoir me semble t il des consequences interressantes.
    Oui mais il suffit de prendre une surface suffisamment tordue pour pouvoir dessiner le graphe sans croisement autre qu'aux sommets (ruban de Moebius, tore, surface orientée à n "trous"...). (La sphère n'amène rien de plus à ce niveau, si on pique en un point on obtient un plan).
     


    • Publicité



  6. jobherzt

    Date d'inscription
    janvier 2005
    Âge
    31
    Messages
    1 412

    Re : Algorithme de Dijkstra et plus court chemin

    Vu comme ca On peut aussi le plonger dans R^3
     

  7. homotopie

    Date d'inscription
    janvier 2006
    Localisation
    Lille
    Âge
    44
    Messages
    2 523

    Re : Algorithme de Dijkstra et plus court chemin

    Citation Envoyé par jobherzt Voir le message
    On peut aussi le plonger dans R^3
    En effet
     


    • Publicité




Poursuivez votre recherche :




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. integrale de chemin
    Par samira_pg dans le forum Physique
    Réponses: 18
    Dernier message: 17/03/2007, 18h28
  3. Enigme : Le plus court chemin de la fortune
    Par Argyre dans le forum Science ludique : la science en s'amusant
    Réponses: 59
    Dernier message: 30/01/2006, 21h40
  4. électricité et chemin le plus court
    Par j.g dans le forum Physique
    Réponses: 8
    Dernier message: 16/10/2005, 12h08
  5. quelle est le plus court chemin?
    Par stephone dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 12/02/2005, 01h20