Les graphes

Quelques points et des traits pour les relier suffisent pour créer un graphe. Cette grande simplicité est pourtant à l’origine d’un foisonnement mathématiques impressionnant.

Un peu d’histoire

L’acte de naissance de la théorie des graphes date d’une petite énigme à laquelle s’attelaient sans succès les habitants de Königsberg. Comment un voyageur pouvait traverser les sept ponts sans jamais passer deux fois sur le même pont ? Euler résout le problème et fonda du même coup la théorie des graphes !

Un graphe permet d’extraire l’essence du problème : les arêtes sont les ponts et les sommets (ou nœuds) sont les zones accessibles depuis ces ponts (séparées par les bras de rivière).

La forme précise des lignes reliant les points n’a pas d’importance : elles ne font qu’indiquer l’existance de laison entre ces points (cela illustre le caractère topologique et non géométrique du problème).

Euler compris alors que ce qu’on appelerait ensuite un chemin eulérien (un chemin reliant chaque sommet en ne passant qu’une fois par chaque arête) n’est possible que si le graphe ne compte pas plus de deux sommets d’où partent un nombre impair d’arêtes. Or dans le cas de Königsberg, il part un nombre impair d’arêtes de chacun des sept sommets ! Un chemin eulérien y est donc impossible.

Ce premier pas d’Euler eut lieu en 1737, il fallut attendre ensuite plus de cent ans pour que Kirchhoff réutilise des graphes pour déterminer les intensités circulant dans les différentes branches d’un circuit électrique ; il met alors au point la notion d’arbre, des graphes sans boucle, en 1847.

Dix ans plus tard, c’est au tour de la chimie de s’attaquer aux graphes. En 1857, Cayley s’intéresse aux différentes structures possibles (isomères) d’une molécule ayant $n$ atomes de carbone et $2n+2$ atomes d’hydrogène (un alcane). Cela revient à trouver tous les arbres à $3n+2$ éléments tels que de chaque élément (chaque sommet) partent exactement une ou quatre arêtes (symbolisant les liaisons chimiques).

En 1869, enfin, les mathématiciens redécouvrent les graphes, par la voix de Jordan qui, sans connaître les travaux de Cayley, retrouve ses résultats.

Les jeux ne sont pas en reste : en 1859, le mathématicien et physicien irlandais William Hamilton invente “The Icosian Game”, dont le but est de visiter une et une seule fois tous les sommets d’un dodécaèdre régulier. Un tel chemin est depuis appelé hamiltonien.
Apparemment voisin du problème du chemin eulérien (visiter une et une seule fois chaque arête), le problème du chemin hamiltonien est en réalité beaucoup plus difficile.
Pour ce qui est du jeu que vous pouvez tester ci-dessous, une règle supplémentaire impose que la fin du chemin soit adjacente à son début. En rejoignant le point de départ, on formerait alors un cycle et on appelle ainsi cycle hamiltonnien un cycle passant par tous les sommets (pour pimenter les choses, un premier joueur choisit 5 sommets voisins les uns des autres et le deuxième joueur doit alors trouver les 15 restants ; c’est ça le jeu original d’Hamilton¹ , et il a prouvé que la victoire est alors toujours possible pour le deuxième joueur).

Le deuxième moitié du 20^e siècle et l’avènement de l’informatique voit la théorie des graphes prendre son véritable essor : c’est en effet l’outil idéal pour décrire les réseaux complexes modernes.

Les réseaux sont partout : les réseaux sociaux et les réseaux de communication, mais on trouve aussi des réseaux dans des champs scientifiques très différents comme en biologie, logistique, linguistique, économie, etc.

La théorie des graphes donne un langage commun à la description de ces réseaux.

Vocabulaire

Graphes non orientés

Quelques exemples dans des champs variés :

Est représenté ci-dessus le graphe $G=(S,A)$ avec $S=\{1,2,3,4,5,6\}$ et $A=\{\{1,2\},\{1,5\},\{2,5\},\{3,3\},\{4,6\}\}$

Exemple : il y a une boucle sur le sommet $3$.

Exemple : $Adj(2)=\{1,5\}$

Exemple : pour le graphe ci-dessus $|S|=6$

Exemple : pour le graphe ci-dessus $|A|=5$

Graphes orientés

Les arêtes d’un graphe non orienté sont symétriques, elles se parcourent indifféremment dans les deux sens, mais ce n’est pas toujours très pertinent. Considérons les exemples suivants :

• Supposons que l’on veuille modéliser un plan routier. On associe naturellement un carrefour à un sommet et une rue à une arête. Mais on a besoin en plus d’une notion de direction pour représenter les rues à sens unique.
• Pour modéliser des relations sociales, une arête entre Alice et Bob modélise un lien, mais comment représenter le fait que Bob connaisse Alice, mais que l’inverse soit faux ?
• Dans un réseau d’ordinateur, en particulier sans fil, le lien entre deux nœuds est généralement non symétrique dans le sens où un message peut être envoyé de A vers B, mais pas l’inverse.

Pour modéliser ce type de situation, on utilise des graphes orientés.

Un graphe orienté permet, par exemple, de résumer les relations dans un chi-fou-mi (ici dans la variante puits montrant bien que jouer “pierre” est sans intérêt, ou encore dans la variante pierre-feuille-ciseaux-lézard-spock de The Big Bang Theory).

Pour “pierre-feuille-ciseaux-puits”, le graphe $G(S,A)$ a pour sommets :

$$S=\{pierre,feuille,ciseaux,puits\}$$

Et pour arêtes :

Degré d’un sommet

Exemple : $d_+(puits)=2$ et $d_-(puits)=1$, d’où $d(puits) = d_+(puits) + d_−(puits)=2+1=3$

$\sum_{s \in S} d_+(s) =\sum_{s \in S} d_-(s) =|A|=6$

Le degré d’un sommet est un concept simple, mais fécond, utilisé dans des contextes très différents. Dans un réseau social, le degré d’un sommet traduit l’importance d’une personne dans le groupe. Dans un réseau de communication comme Internet, on apprend beaucoup sur l’organisation réelle du réseau à partir de la distribution obtenue en ordonnant les sommets par leurs degrés.

Chemin, chaîne, cycle et circuit

Cas des graphes orientés

Soit $G = (S, A)$ un graphe orienté.

• $<6,3,2,1>$ est un chemin du graphe.
• $<1,5,3,2,1>$ est un circuit.

Cas des graphes non orientés

Distance dans un graphe

La notion de longueur de chemin nous permet ensuite de définir la notion de distance dans un graphe.

Exemple : dans le graphe orienté ci-dessus $d(2,3)=2$, $d(3,2)=1$, $d(6,1)=3$ et $d(3,6)=\infty$.

Dans ce graphe taureau, le diamètre vaut 3 (distance entre les deux cornes).

Connexité

Le graphe comportant les sommets $1,2,3,4$ n’est pas connexe mais celui comportant les sommets $5,6,7,8$ l’est !

Représentation d’un graphe

Listes d’adjacence

Soit le graphe $G = (S,A)$ d’ordre $n$. On suppose que les sommets de $S$ sont numérotés de $1$ à $n$.

Dans chaque liste d’adjacence, les sommets sont généralement ordonnés arbitrairement.

Pour l’implémentation Python, on peut soit utiliser des listes imbriquées, soit un dictionnaire.

Exemple :

# Avec un dictionnaire
T = {1:[1,3],2:[1,3,4],3:[],4:[1,2,3,4]}
# Avec des listes imbriquées
T = [[1,3],[1,3,4],[],[1,2,3,4]]

L’avantage du dictionnaire est qu’il n’impose pas d’avoir une correspondance entre le numéro du sommet et la position dans la liste d’adjacence (dans le cas de listes imbriquées T[0] sera toujours la liste correspondant au premier sommet, T[1], celle du deuxième, etc.).

Taille mémoire nécessaire: si le graphe G est orienté, la somme des longueurs des listes d’adjacence est égale au nombre d’arcs de $A$, puisque l’existence d’un arc $(s_i,s_j)$ se traduit par la présence de $s_j$ dans la liste d’adjacence de $T[s_i]$.
En revanche, si le graphe n’est pas orienté, la somme des longueurs de toutes les listes d’adjacence est égale à deux fois le nombre d’arêtes du graphe, puisque si $\{s_i,s_j\}$ est une arête, alors $s_i$ appartient à la liste d’adjacence de $T[s_j]$, et vice versa.

Opérations sur les listes d’adjacence : pour tester l’existence d’un arc $(s_i, s_j)$ ou d’une arête $\{s_i, s_j \}$, on doit parcourir la liste d’adjacence de $T[s_i]$ jusqu’à trouver $s_j$.
En revanche, le calcul du degré d’un sommet, ou l’accès à tous les successeurs d’un sommet, est très efficace : il suffit de parcourir la liste d’adjacence associée au sommet.

Le calcul des prédécesseurs d’un sommet n’est pas pratique avec cette représentation. Il nécessite le parcours de toutes les listes d’adjacences de $T$.
Si l’on a besoin de connaître les prédécesseurs d’un sommet, une solution est de maintenir, en plus de la liste d’adjacence des successeurs, la liste d’adjacence des prédécesseurs.

Matrice d’adjacence

Soit le graphe $G = (S,A)$ d’ordre $n$. On suppose que les sommets de $S$ sont numérotés de $1$ à $n$.

Implémentation Python :

M = [[1,0,1,0],[1,0,1,1],[0,0,0,0],[1,1,1,1]]
# pour savoir si un arc joint le sommet 1 au sommet 3
M[0][2]
# pour savoir si un arc joint le sommet 3 au sommet 1
M[2][0]

Taille mémoire nécessaire :

Opérations sur les matrices d’adjacence :
le test de l’existence d’un arc ou d’une arête avec une représentation par matrice d’adjacence est immédiat (il suffit de tester directement la case correspondante de la matrice).
En revanche, connaître le degré d’un sommet nécessite le parcours de toute une ligne (ou toute une colonne) de la matrice.

Application : Combien y a-t-il de chemins menant d’un sommet à un autre en exactement $n$ coups ?

On cherche donc les chemins de longueur $n$ entre deux sommets $i$ et $j$.
Soit $M = (m_{i,j})$ la matrice d’adjacence d’un graphe $G(S,A)$. $M$ est donc aussi le nombre de chemin de $i$ à $j$ de longueur $1$ (une seul arête), que l’on va noter $m_{i,j}(1)$.
L’idée est alors de découper le chemin de longueur $n$ en un chemin de longueur $n-1$ suivi d’un chemin de longueur $1$. Le nombre $m_{i,j}(n)$ de chemins de longueur $n$ est ainsi donné par : $$ m_{i,j}(n)=\sum_{k=1}^{|S|}m_{i,k}(n-1)\times m_{k,j}(1)$$ Pour $ m_{i,j}(2) $, on obtient $m_{i,j}(n)=\sum_{k=1}^{|S|}m_{i,k}(1)\times m_{k,j}(1)$ qui n’est autre que $M^2$ (on reconnaît en effet la formule du produit matriciel).
Et par une récurrence immédiate, pour des chemins de longueur $n$, il suffit de calculer $M^n$.

Exemple : combien y a-t-il de chemins de longueur 4 entre les sommets 1 et 3 du graphe représenté ci-dessous. La matrice d’adjacence du graphe vaut $M = \begin{pmatrix}1&1&0\\0&0&1\\1&1&0\end{pmatrix}$. Utilisons Python pour calculer $M^4$ :

import numpy as np # librairie très utile pour les calculs sur matrices
from numpy.linalg import matrix_power

M = [[1,1,0],[0,0,1],[1,1,0]]
M = np.array(M) # on convertit M en tableau numpy
M4 = matrix_power(M,4)
print(f"Il y a {M4[2][0]} chemins de longueur 4 du sommet 3 au sommet 1.")

Il y a 3 chemins de longueur 4 du sommet 3 au sommet 1.

Quelques comparaisons

Parcours d’un graphe

Pour déterminer si un sommet est accessible depuis un autre sommet, il faut pouvoir parcourir méthodiquement l’ensemble du graphe.

Algorithme de parcours en largeur (BFS)

Une première méthode, l’algorithme de parcours en largeur (breadth-first BFS), consiste à partir d’un nœud, d’explorer tous ses successeurs, puis les successeurs de chacun de ses successeurs, etc., jusqu’à ce qu’il n’y ait plus de sommets.
Cela revient à inspecter le graphe par couche concentrique de plus en plus éloignées du nœud source.

Pour implémenter un tel algorithme, la structure de données adaptée est la file.

L’idée est de placer chaque nouveau successeur au bout d’une file (enfiler), puis de retirer un à un (défiler) les premiers arrivés (donc les plus proches du sommet de départ) lorsqu’ils sont à leur tour inspectés.

Pour l’implémentation des files, on pourrait utiliser des listes python en ajoutant toujours les éléments à la fin et les retirant au début, mais ce n’est pas très efficace. En effet, l’ajout d’un élément en début de liste à un coût linéaire (proportionnel à la taille de la liste). On aimerant pourtant tirer partie de la structure particulièrement simple des files où seule deux positions (première et dernière) nous intéressent…
Comme souvent en python, un module dédié, ici collecions.deque, va nous venir en aide. Il implément efficacement les files en permettant un enfilage et un défilage en temps constant.

G = {"Bob" : ["Alice","Dave","Charlie"],
     "Alice" : ["Elisa"],
     "Charlie" : ["Elisa","Hector"],
     "Dave" : ["Farid","Gus"],
     "Elisa" : [],
     "Farid" : [],
     "Gus" : [],
     "Hector" : []
     }

from collections import deque

# préconditions: on a besoin d'un graphe G(S,A) représenté par une liste d'adjacence implémentée par un dictionnaire et d'un sommet s de S
# postconditions : un sommet est accessible depuis s si et seulement si il est marqué comme "vu"
def parcours_largeur(G,depart):
    file = deque()
    file.append(depart)
    Vus = {s : False for s in G}
    Sommets = []
    while file: # tant que la file n'est pas vide
        sommet = file.popleft() # méthode de la classe deque permettant de défiler (équivaut à pop(0) sur une liste)
        if not Vus[sommet]: # évite ici d'avoir 2 Elisa, mais ça peut être bien pire
            file += G[sommet]
            Vus[sommet] = True
            Sommets.append(sommet) 
    return Sommets

parcours_largeur(G,"Bob") renvoie ['Bob', 'Alice', 'Dave', 'Charlie', 'Elisa', 'Farid', 'Gus', 'Hector'].

Exemples d’applications du parcours en largeur :

• utilisé par les robots d’exploration des moteurs de recherche pour construire l’index des pages web,
• recherche dans les réseaux sociaux,
• recherche d’un nœud voisin accessible dans les réseaux peer-to-peer.

Algorithme de parcours en profondeur (DFS)

L’idée de l’algorithme de parcours en profondeur (depth-first search DFS) est d’explorer jusqu’au bout chaque chaîne de successeurs du nœud source avant de passer à la suivante.
On n’explore alors plus par couches concentriques mais par branches.

La structure de données dynamique adaptée est cette fois-ci la pile.

def parcours_profondeur(G,depart):
    pile = deque()
    pile.append(depart)
    Vus = {s : False for s in G}
    Sommets = []
    while pile:
        sommet = pile.pop()
        if not Vus[sommet]:
            pile += G[sommet]
            Vus[sommet] = True
            Sommets.append(sommet) 
    return Sommets

parcours_profondeur(G,"Bob") renvoie ['Bob', 'Charlie', 'Hector', 'Elisa', 'Dave', 'Gus', 'Farid', 'Alice'].

Exemples d’applications du parcours en profondeur :

• trouver un chemin entre deux sommets,
• détection de cycles dans un graphe,
• utilisé dans le tri topologique,
• trouver la sortie d’un labyrinthe.

• Que deviendrait la complexité si on remplaçait l’utilisation d’un dictionnaire par celle d’une liste pour vérifier qu’un sommet a déjà été traîté (on utiliserait alors if sommet not in Sommets plutôt que if not Vus[sommet]) ?
• Que deviendrait la complexité sans l’utilisation de la classe deque fournissant une vraie file/pile ?

Structures de données

On remarque que les deux algorithmes de parcours d’un graphe (BFS et DFS) ne diffèrent que par la structure de données utilisée. Et loin d’être anodin, ce passage de la file à la pile change complètement le principe du parcours !
Cela illustre bien que la conception d’un algorithme est intimement liée aux structures de données envisagées.

Nous n’avions pas réellement besoin de la classe deque pour implémenter efficacement la pile. En effet, si insérer un élément au début d’une liste python de taille $n$ a bien un coût linéaire ($O(n)$) et ralentit donc l’exécution par rapport à l’utilisation d’une file, retirer un élément à la fin (via pop) se fait en temps constant ($O(1)$).

Graphes pondérés

Dans de nombreuses situations, les arêtes d’un graphe ne sont pas toutes équivalentes. On ajoute alors l’information du “coût” que cela représente d’emprunter telle ou telle arête. On appelle poids ces valeurs ajoutées aux arêtes/arcs.

Par exemple, pour modéliser un réseau ferroviaire, on peut attribuer à chaque arête modélisant les jonctions entre deux gares la distance correspondante. Et pour un réseau de communication, le poids d’une arête correspondra plutôt au temps nécessaire pour transférer un message de taille élémentaire.

On obtient alors un graphe pondéré.

On utilise par exemple des graphes pondérés, plus particulièrement des arbres de probabilité (où chaque branche est affublée d’une probabilité) pour calculer des probabilités conditionnelles.

Exemple :

Très souvent (particulièrement pour les réseaux de communication), l’information ajoutée au graphe est un temps ou une distance et se pose alors le problème de l’optimisation d’un trajet entre deux sommets.

Problème du plus court chemin

Si le graphe considéré n’est pas pondéré, l’algorithme de parcours en largeur, moyennant quelques adaptations, est tout à fait capable de faire le travail.

Algorithme de parcours en largeur

Comme l’algorithme de parcours en largeur examine le graphe en couches concentriques depuis le sommet de départ, lorsqu’il parvient au sommet cible, on est sûr que le nombre d’arcs est minimal.

Il suffit alors de joindre à la liste des sommets examinés, la liste des chemins permettant de parvenir à chacun de ces sommets (en incrémentant à chaque tour chacun des chemins du sommet correspondant de la nouvelle couche).

def recherche_largeur(G,depart,arrivee):
    file = [(depart,[depart])] # on remplace la file des sommets par une file de tuples (sommet,chemin)
    Vus = {s : False for s in G}
    while file:
        sommet,chemin = file.pop(0) # pop(0) fait la même chose que le popleft des deque
        if sommet == arrivee:
            return chemin # si l'arrivée est atteinte, on retourne le chemin correspondant
        if not Vus[sommet]:
            for s in G[sommet]:
                nv_chemin = chemin + [s]
                file.append((s,nv_chemin))
            Vus[sommet] = True 
    return False # si l'arrivée n'est pas atteinte, on renvoie Faux

G = {"Minimes" : {"Tasdon","Hôpital"},
     "Hôpital" : {"Verdun"},
     "Verdun" : {"Stade"},
     "Tasdon" : {"Cognehors", "Lafond"},
     "Cognehors" : {"Verdun"},
     "Lafond" : {"Mireuil"},
     "Mireuil" : {"Stade"},
     "Stade" : {}
     }

recherche_largeur(G,"Minimes","Stade") retourne bien le chemin comportant le moins d’arêtes : ['Minimes', 'Hôpital', 'Verdun', 'Stade'].

G_pond = {"Minimes" : {"Tasdon": 5,"Hôpital": 4},
          "Hôpital" : {"Verdun": 21},
          "Verdun" : {"Stade": 4},
          "Tasdon" : {"Cognehors": 7, "Lafond": 7},
          "Cognehors" : {"Verdun": 8},
          "Lafond" : {"Mireuil": 5},
          "Mireuil" : {"Stade": 3},
          "Stade" : {}
          }

recherche_largeur(G_pond,"Minimes","Stade") retourne à nouveau ['Minimes', 'Hôpital', 'Verdun', 'Stade'] alors qu’il y a maintenant des chemins plus rapides !

Algorithme de Dijkstra

L’algorithme de Dijkstra va permettre de dépasser les limites du parcours en largeur grâce à un score attribué à chaque sommet (au départ, tous les scores sont fixés à l’infini sauf celui du sommet de départ, fixé à zéro). En sortie de l’algorithme, chaque score vaudra la distance entre le sommet et le sommet de départ.

Comme avec les parcours en largeur et en profondeur, la distinction principale réside dans la sélection du prochain sommet ajouté à Vus ; il s’agit maintenant de celui ayant le plus petit score parmi les sommets non déjà inspectés.

À chaque sommet ajouté $s$, on met à jour les scores de chaque successeur $s_+$ en gardant la valeur minimale entre le score qu’il avait précédemment et la somme entre le score de $s$ et le poids de l’arc $(s,s_+)$ (c’est l’étape de relaxation des arêtes) : $\text{score}(s_+)=\min\left(\text{score}(s_+),\text{score}(s)+p((s,s_+))\right)$

Et en gardant à chaque mise-à-jour du score la trace du nouveau prédécesseur, on obtient un algorithme capable de fournir les distances et les plus courts chemins entre le sommet de départ et tous les autres.

# préconditions : un graphe orienté pondéré G(S,A) avec des poids positifs pour chaque arc représenté par une liste d’adjacence grâce à un dictionnaire, un sommet s_0 de S

# postcondition : pour chaque sommet s_i de S le score trouvé correspond bien à la distance entre s_0 et s_i (d(s_0,s_i))

def sommet_suivant(scores,nonvus):
    """
    retourne le sommet de nonvus au plus bas score
    """
    plus_bas_score = float("inf")
    sommet_choisi = None
    for sommet in nonvus:
        score = scores[sommet]
        if score < plus_bas_score:
            plus_bas_score = score
            sommet_choisi = sommet
    return sommet_choisi

def Dijkstra(G,depart):
    # on construit Scores et Preds  dans lesquels on mettra à jour les scores calculés et les prédecesseurs des sommets examinés
    Scores = {}
    Preds = {}
    # initialisation
    for s in G:
        Scores[s] = float("inf")
        Preds[s] = None
    Scores[depart] = 0
    NonVus = list(G.keys()) # liste pour stocker les sommets examinés
    sommet = depart 
    while sommet is not None:
        score = Scores[sommet]
        Succ = G[sommet]
        for n in Succ:
            nv_score = score + Succ[n]
            if Scores[n] > nv_score:
                Scores[n] = nv_score
                Preds[n] = sommet
        NonVus.remove(sommet)
        sommet = sommet_suivant(Scores,NonVus)
    return Preds,Scores

preds,scores = Dijkstra(G_pond,"Minimes")
print(preds)
print(scores)

# Ce qui s'affiche :

{'Minimes': None, 'Hôpital': 'Minimes', 'Verdun': 'Cognehors', 'Tasdon': 'Minimes', 'Cognehors': 'Tasdon', 'Lafond': 'Tasdon', 'Mireuil': 'Lafond', 'Stade': 'Mireuil'}
{'Minimes': 0, 'Hôpital': 4, 'Verdun': 20, 'Tasdon': 5, 'Cognehors': 12, 'Lafond': 12, 'Mireuil': 17, 'Stade': 20}

En effet, deux actions sont réalisées dans la boucle principale qui parcourt chaque sommet :

• La recherche du sommet non validé ayant un score minimal et sa validation. Elle se fait via la fonction sommet_suivant qui est en $O(n)$.
• La mise à jour des scores des sommets. Elle se fait en temps constant mais concerne tous les successeurs du sommet étudié.

On obtient :

Comme évoqué plus haut, on peut améliorer la complexité en utilisant une structure de données adaptée au problème : la file de priorité implémentée par un tas.
L’idée est d’optimiser le choix du prochain sommet inspecté, celui au plus bas score parmi les sommets pas encore validés. En effet, réinspecter systématiquement toute la liste des sommets restants (c’est ce que fait la fonction sommet_suivant) gaspille de l’information. C’est sur ce point que le tas vient à la rescousse :
le tas est une structure de données de type arbre qui permet de retrouver directement l’élément que l’on veut traiter en priorité. Le tas garde en permanence le sommet de plus bas score en son sommet avec un coût logarithmique.

Conséquence : si on remplace la fonction sommet_suivant par un tas et ses opérations dédiées d’ajout et d’extraction, on passe d’une complexité linéaire à une complexité logarithmique pour cette opération.

import heapq # module implémentant un tas (heap en anglais)

def Dijkstra_tas(G, depart):
    Scores = {sommet: float('infinity') for sommet in G}
    Preds = {sommet: None for sommet in G}
    Scores[depart] = 0
    tas = [(0, depart)]
    # liste de tuples contenant le score et le sommet associé
    # le score correspond alors à la priorité du tas
    while tas:
        score_actuel, sommet_actuel = heapq.heappop(tas)
        # on retire le sommet prioritaire du tas
        if score_actuel == Scores[sommet_actuel]:
        # permet de vérifier que le sommet correspond bien à la dernière mise-à-jour        
            score_voisins = G[sommet_actuel]
            for voisin in score_voisins:
                score = score_actuel + score_voisins[voisin]
                if score < Scores[voisin]:
                    Scores[voisin] = score
                    Preds[voisin] = sommet_actuel
                    heapq.heappush(tas, (score, voisin))
                    # on ajoute le score et le sommet au tas
                    # le même sommet peut être ajouté plusieurs fois avec des scores différents
    return Preds,Scores

En effet, le tas contient $O(m)$ éléments (les voisins mis-à-jour), donc les opérations heappop et heappush sont en $O(\log m)=O(\log n)$.

On entre au pire $m$ fois dans la boucle while, mais la boucle for n’est exécutée que $n$ fois car la condition score_actuel <= Scores[sommet_actuel] nous assure de ne traiter qu’une seule fois chaque sommet.

On verra dans le TP comment encore améliorer les choses grâce à l’utilisation d’une heuristique. On passe alors de l’algorithme de Dijkstra à l’algorithme A* (A star ou A étoile).