Algorithme de Dijsktra

Représentation du graphe par dictionnaire

On décide de représenter un graphe (orienté, et aux arcs pondérés par des poids positifs) par listes de successeurs sous la forme ci-dessous.

Chaque sommet du graphe est une clé du dictionnaire g, dont la valeur associée est la liste des arcs vers les ses voisins.

Un arc est ici représenté par un tuple contenant le sommet voisin et le poids de l'arc.

g= {
    'S': [ ('A', 19), ('B', 8) ],
    'A': [ ('B', 14), ('D', 6) ],
    'B': [ ('C',  4), ('D', 22) ],
    'C': [ ('A',  2), ('D', 10), ('T', 11) ],
    'D': [ ('T',  2) ],
    'T': [ ]
}

Ce graphe est dessiné dans les figures de la section ci-dessous. On souhaite implémenter l'algorithme de Dijkstra sur un tel graphe.

Déroulé de l'algorithme de Dijkstra

Supposons que l'on dispose d'un algorithme de Dijkstra d de type class Dijkstra, construisant un arbre de plus courts chemins sur le graphe g en prenant 'S' pour sommet source. On obtient successivement les étapes suivantes:

Inititialisation:

À l'initialisation de l'algorithme d:

Tous les sommets v sont réputés à distance infinie du sommet source 'S', sauf 'S' qui est réputé à distance nulle de lui-même. Sur le dessin ci-contre, la distance d'un sommet à 'S' est indiquée sous son étiquette. L'algorithme d maintient un dictionnaire d.distances tel que pour tout sommet v, l'entrée d.distances[v] est la distance réputée de 'S' à v. On a donc:
```
# here, we note Inf for math.inf
d.distances == { 'S':0   , 'A':Inf , 'B':Inf , 'C':Inf , 'D':Inf , 'T':Inf  } # after init
```
Aucune distance réputée n'est a priori la distance définitive, pas même pour la source 'S'. Sur le dessin ci-contre, cela se traduit par le fait qu'aucun sommet n'est colorié en vert. L'algorithme d maintient un dictionnaire d.steps tel que pour tout sommet v, l'entrée d.steps[v] est le numéro de l'étape au cours de laquelle la distance réputée de v est devenue définitive, ou None si cette étape est encore à venir. On a donc:
```
d.steps     == { 'S':None, 'A':None, 'B':None, 'C':None, 'D':None, 'T':None } # after init
```
L'arbre des courts chemins ne contient aucun arc. Sur le dessin ci-contre, cela se traduit par le fait qu'aucun arc n'est tracé en rouge. L'algorithme d maintient un dictionnaire d.parents tel que pour tout sommet v, l'entrée d.parents[v] est le sommet parent de v dans l'arbre, où None si ce parent n'existe pas. On a donc:
```
d.parents   == { 'S':None, 'A':None, 'B':None, 'C':None, 'D':None, 'T':None } # after init
```

Après l'initialisation, l'algorithme a autant d'étapes que de sommets. Sur l'exemple, il a donc 6 étapes numérotées de 0 à 5. Au cours de chaque étape, la distance réputée d'un sommet v devient définitive, et on met à jour les voisins de v. Ce sommet v est celui qui a la distance réputée finie et minimale parmi tous les sommets w pour lesquels d.steps[w] == None, c'est-à-dire pour lesquels la distance réputée n'est pas encore définitive.

Étape 0: la distance réputée de 'S' devient définitive

À l'étape 0, le sommet 'S' a une distance réputée finie d.distances['S'] == 0, ce qui est minimal parmi tous les sommets w tels que d.steps[w] == None, c'est-à-dire 'S', 'A', 'B', 'C', 'D', 'T'. Cette distance devient donc définitive. Sur le dessin ci-contre, cela se traduit par le sommet 'S' colorié en vert. Les informations des voisins jaunes de 'S' sont mises à jour ('A' et 'B'). On a donc les changements suivants:

d.steps['S']= 0.
d.parents['A']= 'S' et d.distances['A']= 0+19= 19, car 19 < Inf.
d.parents['B']= 'S' et d.distances['B']= 0+ 8= 8, car 8 < Inf.

À la fin de l'étape 0, l'algorithme d est dans l'état suivant:

d.steps     == { 'S':0   , 'A':None, 'B':None, 'C':None, 'D':None, 'T':None } # after step 0
d.parents   == { 'S':None, 'A':'S' , 'B':'S' , 'C':None, 'D':None, 'T':None } # after step 0
d.distances == { 'S':0   , 'A':19  , 'B':8   , 'C':Inf , 'D':Inf , 'T':Inf  } # after step 0

Étape 1: la distance réputée de 'B' devient définitive

À l'étape 1, le sommet 'B' a une distance réputée finie d.distances['B'] == 8, ce qui est minimal parmi tous les sommets w tels que d.steps[w] == None, c'est-à-dire 'A', 'B', 'C', 'D', 'T'. Cette distance devient donc définitive. Sur le dessin ci-contre, cela se traduit par le sommet 'B' colorié en vert. Les informations des voisins jaunes de 'B' sont mises à jour ('C' et 'D'). On a donc les changements suivants:

d.steps['B']= 1.
d.parents['C']= 'B' et d.distances['C']= 8+ 4= 12, car 12 < Inf.
d.parents['D']= 'B' et d.distances['D']= 8+22= 30, car 30 < Inf.

À la fin de l'étape 1, l'algorithme d est dans l'état suivant:

d.steps     == { 'S':0   , 'A':None, 'B':1   , 'C':None, 'D':None, 'T':None } # after step 1
d.parents   == { 'S':None, 'A':'S' , 'B':'S' , 'C':'B' , 'D':'B' , 'T':None } # after step 1
d.distances == { 'S':0   , 'A':19  , 'B':8   , 'C':12  , 'D':30  , 'T':Inf  } # after step 1

Étape 2: la distance réputée de 'C' devient définitive

À l'étape 2, le sommet 'C' a une distance réputée finie d.distances['C'] == 12, ce qui est minimal parmi tous les sommets w tels que d.steps[w] == None, c'est-à-dire 'A', 'C', 'D', 'T'. Cette distance devient donc définitive. Sur le dessin ci-contre, cela se traduit par le sommet 'C' colorié en vert. Les informations des voisins jaunes de 'C' sont mises à jour ('A', 'D' et 'T'). On a donc les changements suivants:

d.steps['C']= 2.
d.parents['A']= 'C' et d.distances['A']= 12+ 2= 14, car 14 < 19.
d.parents['D']= 'C' et d.distances['D']= 12+10= 22, car 22 < 30.
d.parents['T']= 'C' et d.distances['T']= 12+11= 23, car 23 < Inf.

À la fin de l'étape 2, l'algorithme d est dans l'état suivant:

d.steps     == { 'S':0   , 'A':None, 'B':1   , 'C':2   , 'D':None, 'T':None } # after step 2
d.parents   == { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'C' , 'T':'C'  } # after step 2
d.distances == { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':22  , 'T':23   } # after step 2

Étape 3: la distance réputée de 'A' devient définitive

À l'étape 3, le sommet 'A' a une distance réputée finie d.distances['A'] == 14, ce qui est minimal parmi tous les sommets w tels que d.steps[w] == None, c'est-à-dire 'A', 'D', 'T'. Cette distance devient donc définitive. Sur le dessin ci-contre, cela se traduit par le sommet 'A' colorié en vert. Les informations des voisins jaunes de 'A' sont mises à jour ('D'). On a donc les changements suivants:

d.steps['A']= 3.
d.parents['D']= 'A', et d.distances['D']= 14+ 6= 20, car 20 < 22.

À la fin de l'étape 3, l'algorithme d est dans l'état suivant:

d.steps     == { 'S':0   , 'A':3   , 'B':1   , 'C':2   , 'D':None, 'T':None } # after step 3
d.parents   == { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'A' , 'T':'C'  } # after step 3
d.distances == { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':20  , 'T':23   } # after step 3

Étape 4: la distance réputée de 'D' devient définitive

À l'étape 4, le sommet 'D' a une distance réputée finie d.distances['D'] == 20, ce qui est minimal parmi tous les sommets w tels que d.steps[w] == None, c'est-à-dire 'D', 'T'. Cette distance devient donc définitive. Sur le dessin ci-contre, cela se traduit par le sommet 'D' colorié en vert. Les informations des voisins jaunes de 'D' sont mises à jour ('T'). On a donc les changements suivants:

d.steps['A']= 4.
d.parents['T']= 'D' et d.distances['T']= 20+ 2= 22 car 22 < 23.

À la fin de l'étape 4, l'algorithme d est dans l'état suivant:

d.steps     == { 'S':0   , 'A':3   , 'B':1   , 'C':2   , 'D':4   , 'T':None } # after step 4
d.parents   == { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'A' , 'T':'D'  } # after step 4
d.distances == { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':20  , 'T':22   } # after step 4

Étape finale 5: la distance réputée de 'T' devient définitive

À l'étape finale 5, le sommet 'T' a une distance réputée finie d.distances['T'] == 22, ce qui est minimal parmi tous les sommets w tels que d.steps[w] == None, c'est-à-dire 'T' seul. Cette distance devient donc définitive. Sur le dessin ci-contre, cela se traduit par le sommet 'T' colorié en vert. Les informations des voisins jaunes de 'D' sont mises à jour (mais il n'y en a pas). On a donc les changements suivants:

d.steps['T']= 5.

À la fin de l'étape finale 5, l'algorithme d est dans l'état suivant:

d.steps     == { 'S':0   , 'A':3   , 'B':1   , 'C':2   , 'D':4   , 'T':5   } # after step 5 
d.parents   == { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'A' , 'T':'D' } # after step 5
d.distances == { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':20  , 'T':22  } # after step 5

Implémentation de la classe `Dijkstra`

On souhaite créer une classe Dijkstra pour l'algorithme de même nom :

class Dijkstra (object):
    __slots__= (
        "graph", "source",
        "steps", "distances", "parents"
    )

    def __init__ (self): pass
    def run_step (self, step): pass
    def run (self): pass

d= Dijkstra (g, 'S')
d.run()
print (d.steps)
print (d.distances)
print (d.parents)

L'appel au constructeur d= Dijkstra (g, 'S') construit l'instance d afin que d.graph et d.source soient initialisés avec g et 'S' .

L'appel à la méthode d.run() lance l'algorithme en lui-même et fabrique la solution dans les champs d.steps, d.distances, et d.parents.

Il consiste pour l'essentiel à appliquer une étape via run_step() tant qu'il existe des sommets v avec une distance réputée d.distances[v] finie tel que d.steps[v] == None.

On propose le découpage en méthodes auxiliaires suivant:

class Dijkstra (object):
    __slots__= (
        "graph", "source",
        "steps", "distances", "parents"
    )

    def __init__ (self, graph, source): pass
    def run (self): pass

    def init_tree (self): pass
    def run_step (self, step): pass
    def find_min_vertex (self): pass
    def update_vertex_neighbor (self, vertex, neighbor, arc_length): pass 
    def update_all_vertex_neighbors (self, vertex): pass

La méthode __init__() se contente d'initialiser les données en entrée, c'est-à-dire self.graph et self.source.
La méthode run() lance l'algorithme en lui même.
La méthode init_tree() initialise self.steps, self.distances et self.parents avant le lancement de la première étape de l'algorithme. Elle est invoquée en premier par run().
La méthode run_step() effectue l'étape numéro step de l'algorithme. La fonction renvoie aussi le sommet choisi lors de cette étape, ou None si aucun sommet restant à traiter n'est à distance finie.
La méthode find_min_vertex() est utilisée par run_step() et retourne le prochain sommet à choisir pour cette étape, ou None si aucun sommet restant à traiter à n'est à distance finie.
La méthode update_vertex_neighbor() met à jour les informations d'un voisin neighbor du sommet choisi vertex, lorsque l'arc de vertex à neighbor a pour longueur arc_length.
La méthode update_all_vertex_neighbors() met à jour les informations de tous les voisins du sommet choisi vertex.

On peut tester les étapes successives de l'algorithme avec la fonction de test suivante:

def test_dijkstra():
    g= {
        'S': [ ('A', 19), ('B', 8) ],
        'A': [ ('B', 14), ('D', 6) ],
        'B': [ ('C',  4), ('D', 22) ],
        'C': [ ('A',  2), ('D', 10), ('T', 11) ],
        'D': [ ('T',  2) ],
        'T': [ ]
    }
    min_vertex_list= [ 'S', 'B', 'C', 'A', 'D', 'T' ] # expected order for steps
    steps_list = [
        { 'S':0   , 'A':None, 'B':None, 'C':None, 'D':None, 'T':None }, # after step 0
        { 'S':0   , 'A':None, 'B':1   , 'C':None, 'D':None, 'T':None }, # after step 1
        { 'S':0   , 'A':None, 'B':1   , 'C':2   , 'D':None, 'T':None }, # after step 2
        { 'S':0   , 'A':3   , 'B':1   , 'C':2   , 'D':None, 'T':None }, # after step 3
        { 'S':0   , 'A':3   , 'B':1   , 'C':2   , 'D':4   , 'T':None }, # after step 4
        { 'S':0   , 'A':3   , 'B':1   , 'C':2   , 'D':4   , 'T':5    }, # after step 5
    ]
    Inf= math.inf   
    distances_list = [
        { 'S':0   , 'A':19  , 'B':8   , 'C':Inf , 'D':Inf , 'T':Inf  }, # after step 0
        { 'S':0   , 'A':19  , 'B':8   , 'C':12  , 'D':30  , 'T':Inf  }, # after step 1
        { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':22  , 'T':23   }, # after step 2
        { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':20  , 'T':23   }, # after step 3
        { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':20  , 'T':22   }, # after step 4
        { 'S':0   , 'A':14  , 'B':8   , 'C':12  , 'D':20  , 'T':22   }, # after step 5
    ]
    parents_list = [
        { 'S':None, 'A':'S' , 'B':'S' , 'C':None, 'D':None, 'T':None }, # after step 0
        { 'S':None, 'A':'S' , 'B':'S' , 'C':'B' , 'D':'B' , 'T':None }, # after step 1
        { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'C' , 'T':'C'  }, # after step 2
        { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'A' , 'T':'C'  }, # after step 3
        { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'A' , 'T':'D'  }, # after step 4
        { 'S':None, 'A':'C' , 'B':'S' , 'C':'B' , 'D':'A' , 'T':'D'  }, # after step 5
    ]
        
    d= Dijkstra (g, 'S')
    d.init_tree()
    for k in range (0, 6):
        min_vertex= d.run_step(k)
        assert min_vertex  == min_vertex_list[k]
        assert d.distances ==  distances_list[k]
        assert d.parents   ==    parents_list[k]
        assert d.steps     ==      steps_list[k]
   
test_dijkstra()

Algorithme de Dijsktra

Représentation du graphe par dictionnaire

Déroulé de l'algorithme de Dijkstra

Implémentation de la classe Dijkstra

Implémentation de la classe `Dijkstra`