Cours – Graphes en Python : parcours et plus court chemin
BTS SIO SISR 2e année – Pour aller plus loin – S17 – à lire avant les exercices
Ce que tu dois savoir déjà
- Prérequis : file (
deque) et dictionnaire (S16) ; parcours en profondeur (S10) ; graphes de la 1re année. - Outils : Papier, éditeur Python intégré au site
À la fin de ce cours tu sauras
- Représenter un graphe orienté, pondéré ou non ;
- Écrire un parcours en largeur ;
- Écrire l'algorithme de Dijkstra ;
- Évaluer leur complexité ;
- Tester sur un petit réseau.
I. Représenter un graphe
Graphe non pondéré : dictionnaire sommet → liste de voisins (comme en S10).
g : une flèche va d'un sommet vers l'un de ses voisins. Le cycle A → C → E → A est celui qui oblige à mémoriser les sommets visités.Graphe pondéré : dictionnaire sommet → dictionnaire voisin → poids (coût d'une liaison : latence en ms, distance...).
gp : le nombre sur une flèche est son poids (par exemple une latence en ms).II. Parcours en largeur (BFS)
Le parcours en largeur visite d'abord les voisins du départ, puis les voisins des voisins, etc. Il utilise une file.
from collections import deque
def bfs(g, depart):
vus = [depart]
file = deque([depart])
while file:
s = file.popleft()
for v in g[s]:
if v not in vus:
vus.append(v)
file.append(v)
return vus
Depuis "A" dans g : ["A", "B", "C", "D", "E"]. Les sommets sont visités par distance croissante (en nombre de liaisons) : c'est ce qui donne le plus court chemin en nombre de sauts, ce que le parcours en profondeur ne garantit pas.
Pour retrouver un chemin, on mémorise le parent de chaque sommet à sa première découverte, puis on remonte du but vers le départ.
Note
La liste vus rend le test v not in vus coûteux ; avec un ensemble (set) il devient \(O(1)\) en moyenne. Le nombre d'opérations est de l'ordre de \(n + m\) (sommets plus liaisons), d'après l'analyse classique du parcours en largeur.
III. Plus court chemin pondéré : Dijkstra
Quand les liaisons ont un coût positif ou nul, on utilise l'algorithme de Dijkstra :
- distance du départ = 0, les autres = infini ;
- on prend le sommet non traité de plus petite distance ;
- on met à jour (on relâche) la distance de ses voisins :
d[v] = min(d[v], d[s] + poids); - on recommence jusqu'à épuisement.
import heapq
def dijkstra(g, depart):
dist = {depart: 0}
tas = [(0, depart)]
while tas:
d, s = heapq.heappop(tas)
if d > dist[s]:
continue
for v, w in g[s].items():
nd = d + w
if v not in dist or nd < dist[v]:
dist[v] = nd
heapq.heappush(tas, (nd, v))
return dist
Trace sur gp depuis A.
| Étape | Sommet traité | Distances connues |
|---|---|---|
| 0 | A = 0 | |
| 1 | A | B = 4, C = 1 |
| 2 | C (1) | B = 3 (via C), D = 6 |
| 3 | B (3) | D = 4 (via B) |
| 4 | D (4) | rien à améliorer |
Résultat : {"A": 0, "C": 1, "B": 3, "D": 4}. Le plus court chemin de A à D est A → C → B → D, de coût 4.
Warning
Dijkstra suppose des poids positifs ou nuls. Avec un poids négatif, la distance d'un sommet déjà traité peut encore baisser : l'algorithme n'est plus correct.
Un tas (heapq) donne un coût de l'ordre de \((n + m)\log n\), d'après l'analyse classique de l'algorithme.
IV. Choisir
| Besoin | Algorithme |
|---|---|
| Atteindre / explorer | profondeur ou largeur |
| Plus court en nombre de sauts | largeur |
| Plus court en coût (poids \(\ge 0\)) | Dijkstra |
Test flash. Quelle est la distance de A à D dans gp si le poids de C → B passe de 2 à 5 ?
Voir la réponse
Trois chemins : A → B → D = 4 + 1 = 5 ; A → C → B → D = 1 + 5 + 1 = 7 ; A → C → D = 1 + 5 = 6. Minimum : 5.
À retenir
- Largeur : file, plus court en nombre de sauts.
- Dijkstra : plus court en coût, poids \(\ge 0\), on traite le sommet de distance minimale.
- On retrouve le chemin grâce aux parents.