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 'C' pour obtenir l'arbre des plus courts chemins en partant de ce sommet.
    Arbre des plus courts chemins en partant du sommet 'C' :
    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 'C' pour lequel on stocke 0) et dans la colonne parent on laisse vide pour commencer.

    SommetPoidsParent
    A
    B
    C0
    D
    E
    F
    G

    Étape 2

    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 ('D', 'E', 'F', 'G') 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
    A
    B
    C0
    D9C
    E13C
    F9C
    G24C

    Étape 3

    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', 'C', 'E', '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
    A37D
    B16D
    C0
    D9C
    E13C
    F9C
    G24C

    Étape 4

    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', '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
    A25F
    B16D
    C0
    D9C
    E13C
    F9C
    G24C

    Étape 5

    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', 'B', 'C', 'D') 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
    A25F
    B16D
    C0
    D9C
    E13C
    F9C
    G24C

    Étape 6

    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', 'E', 'F', 'G') 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
    A25F
    B16D
    C0
    D9C
    E13C
    F9C
    G19B

    Étape 7

    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 ('B', 'C', '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
    A25F
    B16D
    C0
    D9C
    E13C
    F9C
    G19B

    Étape 8

    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', 'D', 'E', 'F') 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
    A25F
    B16D
    C0
    D9C
    E13C
    F9C
    G19B
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