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

    SommetPoidsParent
    A
    B
    C
    D
    E
    F
    G0

    Étape 2

    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', 'E', '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
    A
    B30G
    C9G
    D
    E22G
    F16G
    G0

    Étape 3

    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', '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
    A12C
    B30G
    C9G
    D25C
    E19C
    F12C
    G0

    É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', '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
    A12C
    B25F
    C9G
    D25C
    E19C
    F12C
    G0

    Étape 5

    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') 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
    A12C
    B25F
    C9G
    D14A
    E19C
    F12C
    G0

    Étape 6

    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', 'C', 'E', 'F') 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
    A12C
    B25F
    C9G
    D14A
    E19C
    F12C
    G0

    Étape 7

    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', 'D', 'F', 'G') 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
    A12C
    B25F
    C9G
    D14A
    E19C
    F12C
    G0

    É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', '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
    A12C
    B25F
    C9G
    D14A
    E19C
    F12C
    G0
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