M07 - Graphes et plus court chemin

M07 - Théorie des graphes : matrices, chemins, circuits, niveaux, Dijkstra

Objectif

Lire et construire la matrice d’adjacence, compter les chemins de longueur $k$ avec $M^k$, trouver les circuits et la fermeture transitive, ranger par niveaux, et calculer un plus court chemin (Dijkstra - la base du routage OSPF).

---

1. Vocabulaire

Terme	Définition
Sommet	Un point (routeur, page web, tâche…)
Arête	Liaison non orientée (graphe non orienté)
Arc	Liaison orientée $u\to v$ (graphe orienté)
Successeur / prédécesseur de $v$	$w$ tel que $v\to w$ / $u$ tel que $u\to v$
Chemin	Suite d’arcs qui s’enchaînent ; longueur = nombre d’arcs
Circuit	Chemin qui revient à son point de départ (boucle = circuit de longueur 1)
Graphe pondéré	Chaque arc a un poids (distance, coût, durée)
Degré	Nombre d’arêtes touchant un sommet (somme des degrés = 2 × nb d’arêtes)

2. Matrice d’adjacence

$m_{i,j}=1$ s’il existe un arc de $i$ vers $j$, sinon 0 (sommets dans l’ordre alphabétique).

flowchart LR
  A((A)) --> B((B))
  A --> C((C))
  B --> D((D))
  D --> A
  D --> E((E))
  E --> D

$M=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1\\ 0& 0& 0& 1& 0\end{array}\right)\begin{array}{c}\leftarrow A\\ \leftarrow B\\ \leftarrow C\\ \leftarrow D\\ \leftarrow E\end{array}$

Lecture	Donne
Ligne $i$	Successeurs de $i$ (somme = nombre de successeurs)
Colonne $j$	Prédécesseurs de $j$
Matrice symétrique	Graphe non orienté
Ligne de 0	Sommet sans successeur (ici C)

3. Puissances : compter les chemins

Théorème

Le terme $(i,j)$ de $M^k$ = nombre de chemins de longueur $k$ de $i$ vers $j$. Somme de la diagonale de $M^k$ = nombre de circuits de longueur $k$ (comptés depuis chaque sommet de départ).

4. Fermeture transitive

$\hat{M}=M\oplus M^{[2]}\oplus \cdots \oplus M^{[n]}$ ($\oplus$ = OU terme à terme, $M^{[k]}$ = puissance booléenne). ${\hat{m}}_{i,j}=1⟺$ il existe au moins un chemin de $i$ vers $j$.

• Un 1 sur la diagonale de $\hat{M}$ → le sommet est sur un circuit.
• Diagonale entièrement nulle → graphe sans circuit (nécessaire pour un ordonnancement → M08 - Ordonnancement MPM).

5. Niveaux (graphe sans circuit)

Niveau 0 = sommets sans prédécesseur ; on les retire ; les nouveaux sommets sans prédécesseur forment le niveau 1, etc.

Exemple BTS 2019 (A→B, A→C, B→D, C→E, D→E, D→F, E→F) :

Niveau	Sommets
0	A
1	B, C
2	D
3	E
4	F

Sa fermeture transitive a une diagonale nulle → aucun circuit ✅.

6. Plus court chemin : algorithme de Dijkstra

Principe : on part de la source à distance 0 ; à chaque étape on fixe le sommet non fixé de plus petite distance, puis on met à jour ses voisins si on trouve plus court en passant par lui. (Poids positifs uniquement.)

flowchart LR
  A((A)) ---|4| B((B))
  A ---|2| C((C))
  C ---|1| B
  B ---|5| D((D))
  C ---|8| D
  C ---|10| E((E))
  D ---|2| E
  D ---|6| F((F))
  E ---|2| F

Étape	Fixé	A	B	C	D	E	F
0	A	0	4 (A)	2 (A)	∞	∞	∞
1	C	–	3 (C)	2 (A)	10 (C)	12 (C)	∞
2	B	–	3 (C)	–	8 (B)	12 (C)	∞
3	D	–	–	–	8 (B)	10 (D)	14 (D)
4	E	–	–	–	–	10 (D)	12 (E)
5	F	–	–	–	–	–	12 (E)

On remonte les prédécesseurs depuis F : F ← E ← D ← B ← C ← A → A → C → B → D → E → F, longueur 12.

En réseau

OSPF utilise exactement Dijkstra (« Shortest Path First ») : chaque routeur calcule l’arbre des plus courts chemins, avec comme poids le coût des liens (inverse du débit). → P02 - Routage dynamique (RIP, OSPF)

7. Scripts

scripts/maths/graphes_matrices.py - matrice, successeurs/prédécesseurs, $M^k$, circuits, fermeture transitive, niveaux :

python3 graphes_matrices.py "A>B A>C B>D C>E D>E D>F E>F" 3

scripts/maths/dijkstra.py - tableau d’étapes + chemin :

python3 dijkstra.py A F "A-B:4 A-C:2 C-B:1 B-D:5 C-D:8 C-E:10 D-E:2 D-F:6 E-F:2"

#!/usr/bin/env python3
"""Dijkstra minimal (le fichier complet affiche le tableau d'étapes)."""
import heapq
 
 
def dijkstra(graphe: dict, depart: str):
    distances = {s: float("inf") for s in graphe}
    predecesseurs = {s: None for s in graphe}
    distances[depart] = 0
    file_priorite = [(0, depart)]
    while file_priorite:
        distance_courante, sommet = heapq.heappop(file_priorite)
        if distance_courante > distances[sommet]:
            continue
        for voisin, poids in graphe[sommet].items():
            if distance_courante + poids < distances[voisin]:
                distances[voisin] = distance_courante + poids
                predecesseurs[voisin] = sommet
                heapq.heappush(file_priorite, (distances[voisin], voisin))
    return distances, predecesseurs
 
 
graphe_exemple = {}
for origine, destination, poids in [("A","B",4), ("A","C",2), ("C","B",1), ("B","D",5), ("C","D",8),
                                    ("C","E",10), ("D","E",2), ("D","F",6), ("E","F",2)]:
    graphe_exemple.setdefault(origine, {})[destination] = poids     # graphe non orienté :
    graphe_exemple.setdefault(destination, {})[origine] = poids     # on ajoute les deux sens
distances, predecesseurs = dijkstra(graphe_exemple, "A")
chemin, sommet = [], "F"
while sommet:
    chemin.insert(0, sommet)
    sommet = predecesseurs[sommet]
print(" → ".join(chemin), "=", distances["F"])     # A → C → B → D → E → F = 12

Voir aussi

• M06 - Matrices et systèmes · M08 - Ordonnancement MPM · M04 - Ensembles, fonctions et relations
• Retour : 00 - Index général