Algorithme de Dijkstra

Graphe original
Questions
  1. Appliquer l'algorithme de Dijkstra sur le graphe ci-contre en considérant le sommet de départ 'E' pour obtenir l'arbre des plus courts chemins en partant de ce sommet.
    Arbre des plus courts chemins en partant du sommet 'E' :
    Graphe résultat

    Étape 1

    On crée un tableau avec une ligne par sommet, dans la colonne 'poids' on stocke ∞ (sauf pour le point de départ 'E' pour lequel on stocke 0) et dans la colonne parent on laisse vide pour commencer.

    SommetPoidsParent
    A
    B
    C
    D
    E0
    F
    G

    Étape 2

    Le sommet 'E' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('A', 'C', 'F') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'E' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'E'.

    SommetPoidsParent
    A11E
    B
    C16E
    D
    E0
    F24E
    G

    Étape 3

    Le sommet 'A' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('B', 'C', 'D', 'E', 'F', 'G') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'A' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'A'.

    SommetPoidsParent
    A11E
    B38A
    C15A
    D36A
    E0
    F24E
    G12A

    Étape 4

    Le sommet 'G' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('A', 'D', 'F') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'G' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'G'.

    SommetPoidsParent
    A11E
    B38A
    C15A
    D30G
    E0
    F24E
    G12A

    Étape 5

    Le sommet 'C' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('A', 'E', 'F') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'C' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'C'.

    SommetPoidsParent
    A11E
    B38A
    C15A
    D30G
    E0
    F18C
    G12A

    Étape 6

    Le sommet 'F' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('A', 'B', 'C', 'D', 'E', 'G') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'F' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'F'.

    SommetPoidsParent
    A11E
    B38A
    C15A
    D21F
    E0
    F18C
    G12A

    Étape 7

    Le sommet 'D' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('A', 'B', 'F', 'G') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'D' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'D'.

    SommetPoidsParent
    A11E
    B25D
    C15A
    D21F
    E0
    F18C
    G12A

    Étape 8

    Le sommet 'B' a le poids le plus faible parmi les sommets qui n'ont pas encore été traités. On regarde pour chacun des sommets suivants ('A', 'D', 'F') si le poids actuel de ce sommet est supérieur à la somme cumulée du poids du sommet courant 'B' et de la valuation de l'arête entre ces deux sommets. Si c'est le cas, on met à jour le poids et on définit son parent comme étant le sommet actuel 'B'.

    SommetPoidsParent
    A11E
    B25D
    C15A
    D21F
    E0
    F18C
    G12A
Afficher les réponses
Lancer un exercice similaire avec les mêmes paramètres
Lancer un exercice similaire avec des paramètres différents
Lancer un exercice différent
Télécharger le graphe au format GraphVIZ