Dans ce chapitre, on utilise les structures de données du chapitre précédent : piles, files et files de priorité.

I. Les parcours

a) Anatomie d'un parcours

On a besoin d'une structure de données pour stocker des nœuds :

b) Parcours en profondeur : la pile

Voici une implémentation en Python, qui affiche simplement les sommets dans l'ordre. On suppose que le graphe est implémenté par liste d'adjacence :

G = { "a": ["b", "c"],
      "b": ["d", "a", "c"],
      "d": ["b"],
      "c": ["b", "a"]}

Une première idée serait d'écrire :

def parcours_profondeur(G, d):
    pile = [d]
    while len(pile) > 0:
        x = pile.pop()
        print(x)
        for voisin in G[x]:
            pile.append(voisin)

Mais ici, on va ajouter les mêmes sommets à la pile plusieurs fois, et même sans fin s'il y a des cycles ! Il faut retenir les sommets déjà vus :

def parcours_profondeur(G, d):
    pile = [d]
    deja_vu = {d: True}
    while len(pile) > 0:
        x = pile.pop()
        print(x)
        # On ajoute les voisins à la pile
        for voisin in G[x]:
            if voisin not in deja_vu:
                pile.append(voisin)
                #Evite d'ajouter les mêmes sommets à la pile plusieurs fois
                deja_vu[voisin] = True

parcours_profondeur(G, "a")

Pour visualiser le parcours, ordre_affiche récupère la liste des sommets affichés par la fonction, et animer_parcours les allume un par un :

Depuis a, ce parcours visite a, c, b puis d. En rouge, les arêtes par lesquelles chaque sommet a été découvert (l'arborescence du parcours) :

Version récursive :

def parcours_profondeur(G, d, deja_vu):
    # premier appel : parcours_profondeur(G, d, {d: True})
    print(d)
    for voisin in G[d]:
        if voisin not in deja_vu:
            deja_vu[voisin] = True
            parcours_profondeur(G, voisin, deja_vu)

c) Parcours en largeur : la file

from collections import deque

def parcours_largeur(G, d):
    file = deque()
    file.appendleft(d)
    deja_vu = {d: True}
    while len(file) > 0:
        x = file.pop()
        print(x)
        # On ajoute les voisins à la file
        for voisin in G[x]:
            if voisin not in deja_vu:
                file.appendleft(voisin)
                #Evite d'ajouter les mêmes sommets à la file plusieurs fois
                deja_vu[voisin] = True

Sur un graphe un peu plus grand, la différence entre les deux parcours se voit mieux :

Depuis a, ce parcours visite a, b, c puis d. En rouge, les arêtes par lesquelles chaque sommet a été découvert :

II. Plus court chemin

Sur un graphe non pondéré, le parcours en largeur permet de trouver les plus courts chemins depuis un sommet : on augmente la profondeur graduellement (d'abord les sommets à distance 1, puis 2, etc.).

Mais sur un graphe pondéré (un plan, avec des autoroutes, des routes de campagne, etc.), pouvez-vous faire un parcours qui permet de trouver le plus court chemin ?

Idée : plutôt que d'augmenter la profondeur, on augmente la pondération.

a) Algorithme de Dijkstra

En Python :

import math

def dijkstra(G, d):
    """Implemente l'algorithme de Dijkstra sur un graphe par liste d'adjacence.
    Renvoie un dictionnaire qui à chaque sommet associe sa distance à d.
    On utilise une implémentation naïve de file de priorité.
    """
    noeuds = {s: math.inf for s in G.keys()}
    noeuds[d] = 0
    V = {}
    while len(noeuds) > 0:
        # On trouve le plus petit élément de noeuds
        sommet_min = None
        distance_min = math.inf
        for (sommet, distance) in noeuds.items():
            if distance < distance_min:
                distance_min = distance
                sommet_min = sommet
        # Si le sommet minimum est None, c'est qu'on a parcouru toute la composante connexe
        # On peut donc renvoyer le dictionnaire;
        if sommet_min is None:
            return V
        # On le supprime de la liste des noeuds et on l'ajoute au dictionnaire résultat.
        del noeuds[sommet_min]
        V[sommet_min] = distance_min

        # On met à jour la distance des voisins
        for (voisin, poids) in G[sommet_min]:
            if voisin not in V:
                noeuds[voisin] = min(noeuds[voisin], distance_min + poids)
    return V

Sur le graphe de l'exemple : le dictionnaire renvoyé retient les sommets dans l'ordre où ils ont été traités, qu'on peut donc animer.

Pour visualiser ces algorithmes : visualgo.net.

b) A*

L'idée de l'algorithme A* est d'utiliser une heuristique, c'est-à-dire une indication sur le résultat spécifique au problème traité, souvent facile à calculer mais imprécise.

En l'occurrence, cette heuristique est une indication sur la distance minimum qu'il reste pour parvenir au résultat. Pour que notre algorithme reste correct, l'heuristique doit toujours être plus petite que la vraie distance !

Exemple : dans le cas d'une carte, on peut prendre la distance "à vol d'oiseau" ! Quel que soit le chemin emprunté, on ne pourra pas aller plus vite.

Supposons qu'on ait une fonction qui code l'heuristique. Dans ce cas, on ne va plus prendre le sommet de distance à l'origine minimale, mais celui qui minimise ! C'est-à-dire celui qui a le potentiel d'être sur le chemin le plus court.

La complexité de A* n'est pas meilleure que celle de Dijkstra dans le pire cas. Mais dans la majorité des cas réels, cela va beaucoup plus vite !

Comparez les deux algorithmes sur une grille, où l'on se déplace d'une case à une voisine (en bleu, les cases explorées, dans l'ordre où elles sortent de la file de priorité) : A* se dirige vers la cible, alors que Dijkstra explore dans toutes les directions.

Exercices

def accessible(G, d, a):
    vus = {d: True}
    pile = [d]
    while len(pile) > 0:
        x = pile.pop()
        for v in G[x]:
            if v not in vus:
                vus[v] = True
                pile.append(v)
    return a in vus

def distances(G, d):
    dist = {d: 0}
    file = [d]
    while len(file) > 0:
        x = file.pop(0)
        for v in G[x]:
            if v not in dist:
                dist[v] = dist[x] + 1
                file.append(v)
    return dist

def est_connexe(G):
    d = next(iter(G))   # un sommet quelconque
    vus = {d: True}
    pile = [d]
    while len(pile) > 0:
        x = pile.pop()
        for v in G[x]:
            if v not in vus:
                vus[v] = True
                pile.append(v)
    return len(vus) == len(G)

def plus_court_chemin(G, d, a):
    pere = {d: None}
    file = [d]
    while len(file) > 0:
        x = file.pop(0)
        for v in G[x]:
            if v not in pere:
                pere[v] = x
                file.append(v)
    if a not in pere:
        return None
    chemin = [a]
    while chemin[-1] != d:
        chemin.append(pere[chemin[-1]])
    return chemin[::-1]