Scribd Logo
Importer

Bienvenue sur Scribd !

  • 25 vues

    CM 6: Théorie Des Graphes: Calcul Du Plus Court Chemin

    Transféré par

    Daieth

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    CM 6: Théorie Des Graphes: Calcul Du Plus Court Chemin

    Transféré par

    Daieth
    25 vues3 pages

    Titre original

    CM6

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    25 vues3 pages

    CM 6: Théorie Des Graphes: Calcul Du Plus Court Chemin

    Transféré par

    Daieth

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 3

    vendredi 16 février 2024

    CM 6 : Théorie des graphes

    Calcul du plus court chemin :

    G = (E,U,V) graphe orienté valué


    E : ensemble des sommets
    U: ensembles des arrêtes (c,j) appartenant à ExE
    V: ensembles des coûts V(i,j) des arcs

    Le coût d’un chemin entre 2 sommet est la somme des coûts des arcs formant le chemin

    Cas 1 : Cas où les coûts des arêtes est positif ou nul

    3 types de problèmes ->

    A- Étant donné 2 sommets r et t trouver le plus court chemin entre s et t


    B- Trouver tous les chemins les plus courts entre un sommet s et tout les autres
    C- Trouver le plus court entre tous les couples de sommet du graphe

    Pour le problème B il existe 2 familles d’Algorithme :

    Le principe est de calculer pour chaque sommet x une étiquette, pi(x) qui représente
    le plus court chemin de s vers x
    Certains Algorithmes calculent pi(x) de façon dé nitive ( Djikstra )
    Certains le font jusqu’à la dernière itération (Belleman) = programmation dynamique.

    La méthode de Djikstra :

    Principe :

    L’ensemble des sommets est partagé en 2 sous ensemble, S et S ( son complément ).

    S est le sous ensemble des sommets dé nît marqués, ie pi(x) est la valeur la plus courte
    entre s et x

    Le complément S contient tout les sommets k ayant une étiquette provisoire dé nie par :
    Pour tout k E s :
    pi(k) = min( pi(i) + v(i,k) ) i appartenant à S inter Nombre de prédécesseur de k

    L’itération principale sélectionné dans S le sommet j d’étiquette provisoire minimale et le


    marque dé nit
    pi(j) = min(pi(k)) k appartenant au complément de S

    Chaque fois qu’un sommet est dé nitivement marqué on met à jour tous ses successeurs
    non dé ni marqué.

    1
    fi
    fi
    fi
    fi
    fi
    fi
    Exemple :

    Signe in ni = on peut pas encore atteindre le sommet


    On utilise Pi(x) donc ne pas oublier d’additionner toute les étapes précédentes !

    On continue étape par étape :

    Le plus cours chemin de s à D sera :

    D-1->C-2->B-2->A-4->s

    2
    fi
    Algorithme :

    Vous aimerez peut-être aussi