Ch. 2 — Plus courts chemins : Dijkstra

Le graphe valué

Un graphe valué est un triplet G = (S, A, p) où p, la fonction de poids, associe un nombre réel à chaque arête — une distance, un temps, un coût. Le poids d'un chemin (sa valeur, son coût) est la somme des poids de ses arêtes. Ces définitions donnent les deux notions clés :

• un plus court chemin de x à y est un chemin de x à y dont le poids est le plus petit parmi tous les chemins de x à y ;
• la distance de x à y est le poids d'un plus court chemin de x à y.

Motivations : recherche d'itinéraires (un logiciel de navigation modélise le réseau routier par un graphe), planification, optimisation et aide à la prise de décision.

Un plus court chemin n'existe pas toujours

Trois propriétés à connaître :

• il n'est pas unique : plusieurs chemins peuvent avoir le poids minimal ;
• dans un graphe à poids positifs, on peut se limiter aux chemins sans cycle, car un cycle n'ajoute que du poids — le nombre de chemins candidats devient fini ;
• s'il existe un cycle absorbant (un cycle de poids total négatif), aucun plus court chemin n'existe : quel que soit le chemin choisi, on en construit un de plus petit poids en recommençant le cycle.

Un plus court chemin de x à y existe donc toujours si y est accessible depuis x et si le graphe ne contient pas de cycle absorbant. L'arbre des plus courts chemins depuis un sommet s0 est l'arbre orienté de racine s0 dans lequel le chemin de s0 à chaque sommet est un plus court chemin dans le graphe.

L'algorithme de Dijkstra

Entrées : un graphe valué G à poids positifs et un sommet s0. Résultats : la distance de s0 à chaque sommet, et l'arbre des plus courts chemins depuis s0.

soit Dist(y) = +∞ pour tout y sommet de G    // table des distances depuis s0
soit Pred(y) = indéfini pour tout y          // table des prédécesseurs
soit P = ∅                                   // sommets permanents
Dist(s0) = 0
tant qu'il reste des sommets de G hors de P faire
  soit s le sommet hors de P tel que Dist(s) est minimale
  ajouter s à P
  pour tout sommet x successeur de s et hors de P faire
    si Dist(x) > Dist(s) + p((s,x)) alors
      Dist(x) = Dist(s) + p((s,x))
      Pred(x) = s
retourner Dist et l'arbre défini par Pred

Le principe : l'algorithme maintient une estimation (borne supérieure) des distances, exacte pour les sommets dits permanents. À chaque itération, il choisit parmi les sommets non permanents celui d'estimation minimale — le nouveau permanent, car avec des poids positifs aucun détour ne peut faire mieux — puis relâche ses arêtes sortantes : chaque fois que passer par s améliore l'estimation d'un successeur x, Dist(x) et Pred(x) sont mis à jour.

Un déroulement pas à pas

Depuis le sommet a (a et c voisins, puis d via c, etc.) :

Le résultat se lit en deux tableaux : les distances finales et les prédécesseurs, dont les arêtes (colorées sur le dessin) forment l'arbre des plus courts chemins — ici Pred(b) = d, Pred(c) = a, Pred(d) = c, Pred(e) = d, Pred(f) = d.

Choisir le bon algorithme

• Bellman-Ford : moins rapide que Dijkstra, mais supporte les poids négatifs (sans cycle absorbant) ;
• Bellman : plus rapide encore, mais uniquement sur graphes sans cycles (DAG) — cours de la semaine suivante ;
• A* : non exact mais très efficace, calcule rapidement un court chemin à partir d'une disposition spatiale des sommets ;
• Floyd-Warshall : calcule les distances de chaque sommet vers chaque autre ;
• graphe non valué : le parcours en largeur suffit pour le chemin de plus petite longueur.

Grapp : calculer et dessiner

Grapp est un outil en ligne de commande à deux composants : un serveur en tâche de fond (Grapp server &) et des commandes client. On définit un graphe dans un fichier YAML (type diwgraph pour un graphe orienté valué, uwgraph pour non orienté valué — attention à l'indentation et à l'espace après les deux points), puis :

Grapp load graphe.yaml                       # attribue un identifiant g1
Grapp list                                   # graphes chargés et résultats
Grapp draw -graph g1 -to dessing1            # produit dessing1.png
Grapp shortest-path -algorithm Dijkstra -on g1 -from a
Grapp shortest-path -algorithm Dijkstra -on g2 -from b -silent -csv resultat-pcc.csv

La commande shortest-path accepte -algorithm Dijkstra ou Bellman-Ford, -on (identifiant du graphe), -from (sommet source) ; elle affiche la table des distances et celle des prédécesseurs, et -csv l'exporte. Chaque résultat calculé porte un identifiant ri.j, dessinable par draw -result …. Pour charger un graphe modifié sous le même nom : Grapp load -reload graphe.yaml. Les TP de modélisation (entrepôt, robot, Mélinda) se terminent par les tests auto-correctifs Dijkstra sur Moodle.

A retenir

• graphe valué G = (S, A, p) ; poids d'un chemin = somme des poids ; distance = poids du plus court chemin ;
• cycle absorbant = cycle de poids négatif → aucun plus court chemin n'existe ;
• Dijkstra (poids positifs) : tables Dist et Pred, ensemble P des permanents, relâchement des arêtes sortantes du sommet d'estimation minimale ;
• les Pred définissent l'arbre des plus courts chemins depuis la source ;
• poids négatifs → Bellman-Ford ; graphe acyclique → Bellman ; tous-à-tous → Floyd-Warshall ;
• Grapp : load, list, draw, shortest-path -algorithm Dijkstra -on … -from ….