Graphes : parcours, Dijkstra et A*

Un graphe est un ensemble de noeuds (V) reliés par des arêtes (E). Les parcours servent à visiter tous les noeuds ; Dijkstra et A* trouvent les plus courts chemins quand les arêtes ont un poids.

Représenter un graphe

• Liste d'adjacence : pour chaque noeud, la liste de ses voisins. Mémoire O(|V| + |E|) ; idéal pour les graphes peu denses.
• Matrice d'adjacence : un tableau |V| × |V|. Test « u et v sont-ils voisins ? » en O(1), mais mémoire O(|V|²).

Dans les exemples, quand un noeud a plusieurs voisins, on les prend en ordre alphabétique. Le résultat dépend de cette convention : vérifie celle de ton cours.

Parcours en profondeur (DFS)

On va le plus loin possible avant de revenir en arrière. On utilise une pile, ou la récursion.

dfs(u):
    marquer u comme visité
    pour chaque voisin v de u (en ordre):
        si v n'est pas visité: dfs(v)

Graphe d'exemple (non orienté) : A–B, A–C, B–D, C–D, C–F, D–E.

DFS depuis A : A → B → D (premier voisin non visité de B) → C (premier voisin non visité de D) → F. C n'a plus de voisin libre : on revient à D, qui a encore E. Ordre de visite : A, B, D, C, F, E.

Parcours en largeur (BFS)

On visite les noeuds par « couches » : d'abord le départ, puis tous ses voisins, puis les voisins des voisins. On utilise une file (premier entré, premier sorti).

bfs(départ):
    file = [départ] ; marquer départ comme découvert
    tant que la file n'est pas vide:
        u = défiler()
        visiter u
        pour chaque voisin v de u (en ordre):
            si v n'est pas découvert: le marquer et l'enfiler

BFS depuis A sur le même graphe : file [A] → on visite A et on enfile B, C → on visite B et on enfile D → on visite C et on enfile F (D est déjà découvert) → on visite D et on enfile E → F → E. Ordre : A, B, C, D, F, E.

Dans un graphe sans poids, BFS trouve le chemin avec le moins d'arêtes. Les deux parcours coûtent O(|V| + |E|).

Dijkstra : plus courts chemins

Avec des poids positifs, Dijkstra calcule la distance la plus courte du départ à tous les autres noeuds.

1. d(départ) = 0, toutes les autres distances = ∞.
2. Choisir le noeud non visité de plus petite distance. Sa distance devient définitive.
3. Relâcher chacun de ses voisins v : si d(u) + w(u, v) < d(v), alors d(v) = d(u) + w(u, v).
4. Recommencer jusqu'à ce que tous les noeuds atteignables soient visités.

Exemple : arêtes A–B (4), A–C (1), B–C (2), B–D (5), C–D (8), D–E (3), départ A.

Le chemin direct A–B (4) n'est pas le meilleur : passer par C coûte 3. Avec un heap binaire comme file de priorité, Dijkstra coûte O((|E| + |V|) log |V|).

A* : chercher en direction du but

Quand on cherche le chemin vers un seul but, A* ajoute une estimation de la distance restante. Chaque noeud de la liste ouverte a une priorité :

f(n) = g(n) + h(n)

• g(n) : le coût du meilleur chemin connu du départ jusqu'à n (le d(n) de Dijkstra) ;
• h(n) : une estimation du coût de n jusqu'au but (par exemple la distance à vol d'oiseau).

On choisit toujours le noeud ouvert de plus petit f, et on s'arrête quand on choisit le but (pas quand on le découvre).

Exemple : même graphe, de A vers E, avec h(A) = 7, h(B) = 5, h(C) = 6, h(D) = 3, h(E) = 0.

1. Ouvert : A (f = 0 + 7 = 7). On choisit A → B (g 4, f 9) et C (g 1, f 7).
2. On choisit C (f 7) → B s'améliore (g 3, f 8), D (g 9, f 12).
3. On choisit B (f 8) → D s'améliore (g 8, f 11).
4. On choisit D (f 11) → E (g 11, f 11).
5. On choisit E : c'est le but, coût 11.

Une bonne heuristique

• Admissible : h ne surestime jamais le vrai coût restant. A* trouve alors le chemin optimal.
• Cohérente : h(u) ≤ w(u, v) + h(v) pour chaque arête. Un noeud fermé n'a alors jamais besoin d'être rouvert.

Avec h = 0 partout, A* devient exactement Dijkstra. Plus h est proche du vrai coût, moins A* explore de noeuds.

Deux définitions à connaître

• Chemin d'Euler : passe par chaque arête exactement une fois. Il existe si le graphe est connexe et a 0 ou 2 noeuds de degré impair.
• Chemin hamiltonien : passe par chaque noeud exactement une fois. Savoir s'il en existe un est un problème NP-complet.