• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 03/02/2020

Calculez le plus court chemin dans un graphe

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Intéressons-nous au calcul de plus courts chemins lorsque les liens ont une longueur. Nous allons commencer par l’algorithme de Dijkstra.

Découvrez l'algorithme de Dijkstra

Nous avons vu que le parcours en largeur, BFS, calcule un arbre des plus courts chemins à partir d’un point de départ.

À chaque étape, l’algorithme traite un nouveau sommet, le premier dans la file des sommets à traiter. Si le résultat est un arbre des plus courts chemins, c’est parce qu’on traite les sommets dans l’ordre de leur distance à la source.

Ainsi, à chaque itération, la distance que prendra le sommet traité sera soit la même que celle du précédent, soit 1 de plus. Il n’y a pas d’alternative, parce que la distance que l’on considère est le nombre d’arcs à traverser.

Supposons maintenant que les arcs ont des longueurs positives. La longueur d’un chemin est la somme des longueurs de ses arcs. Il vaut mieux prendre un chemin de 3 arcs de longueur 1 chacun, qu’un seul arc de longueur 5.

BFS ne considérant pas cette information, il ne calcule pas des plus courts chemins au sens de cette métrique. Mais si on s’assure qu’à chaque étape on traite toujours le sommet restant le plus proche de la source, on obtiendra bien des plus courts chemins avec le même principe de parcours. C’est l’algorithme de Dijkstra, du nom de son auteur : à chaque étape, on considère le sommet non traité le plus proche du point de départ, on le marque traité et on met à jour ses voisins.

Comment sait-on quel est le sommet le plus proche ?

Supposons que l’algorithme a traité tous les sommets dont la distance à la source est inférieure à une valeur donnée. Le nœud qui nous intéresse est celui qui, parmi tous les voisins des nœuds déjà traités, minimise la somme de la distance à son voisin traité et de la longueur de l’arc vers ce nœud. Pour obtenir cette information rapidement, la méthode de Dijkstra consiste à mettre à jour une estimation de la distance d’un nœud à chaque fois qu’on traite un de ses voisins.

Au départ, tous les nœuds ont une estimation infinie, sauf la source pour qui cela vaut 0. À chaque étape, on traite le nœud u qui a la plus petite estimation. On est alors sûr que l’estimation vaut la vraie distance.

On peut donc mettre à jour l’estimation des voisins v : c’est le minimum entre l’estimation actuelle et la distance de u plus la longueur de u à v.

Toute la finesse de l’algorithme de Dijkstra tient dans la structure de données qui permet d’obtenir efficacement le nœud qui minimise la distance. En théorie algorithmique, il faut utiliser une structure appelée « tas de Fibonacci » que vous pourrez découvrir en ligne.

L’algorithme de Dijkstra ne peut pas être distribué, il faut centraliser toute l’information de distance pour faire le calcul. C’est comme cela que fonctionne le protocole OSPF de routage dans l’Internet en mode « link state », c’est-à-dire que chaque nœud calculant un routage doit d’abord collecter l’état des liens (les longueurs) de tout le réseau.

Découvrez l'algorithme de Bellman-Ford

L'algorithme de Bellman-Ford que nous allons découvrir est théoriquement moins performant mais peut être distribué.

Rappelons que l’algorithme de Dijkstra calcule l’arbre des plus courts chemins en faisant progresser nœud par nœud une sorte de frontière entre les nœuds dont on connaît la distance et les autres. Pour cela, il a besoin d’une connaissance globale des liens.

L’algorithme de Bellman-Ford part d’un autre principe.

Pour n’importe quel nœud, son plus court chemin vers le point de départ se compose d’un lien vers un de ses voisins, suivi du plus court chemin de ce voisin vers le départ. Le « bon » voisin est celui qui minimise la somme de sa distance au point de départ et de la longueur de l’arc qui le relie.

Ainsi, on peut calculer les plus courts chemins avec une vue locale à son voisinage : si un nœud connaît la distance de tous ses voisins et la longueur des ses arêtes incidentes, il sait calculer sa propre distance. Le principe de Bellman-Ford est donc de maintenir une estimation de cette distance.

  • Au début, seul le point de départ connaît sa « vraie » distance, 0.
    Tous les autres l’estiment à plus l’infini. Après une étape, au pire les voisins du point de départ auront mis à jour leur distance. Pour ceux dont c’est le « vrai » plus court chemin, ils ont l’information, même s’ils ne le savent pas.

  • À la deuxième étape, les plus courts chemins qui ne contiennent que deux arcs sont découverts lorsque les nœuds concernés mettent à jour leur distance vers leurs prédécesseurs qui, eux, ont un plus court chemin avec un seul arc.

  • La preuve de l’algorithme fonctionne ainsi par récurrence : à l’étape k, on obtient les plus courts chemins composés de k arcs en mettant à jour la distance des nœuds dont le prédécesseur a un plus court chemin avec k-1 arcs.

Il suffit donc que l’algorithme itère autant de fois que le nombre d’arcs du plus long plus court chemin. On ne connaît hélas pas ce nombre avant d’avoir fini, mais on sait qu’il est plus petit que |V|, le nombre de sommets.

Cet algorithme n’a pas besoin de connaissance globale et peut donc être distribué. Il suffit d’un minimum de synchronisation entre les nœuds pour qu’ils mettent tous à jour leurs distances avant de passer à l’itération suivante.

La complexité algorithmique de Bellman-Ford est donc |V|.|E|. C’est plus que celle de Dijkstra qui est en |E|.log |V|.

Il s’agit ceci dit de complexité asymptotique et la mise en œuvre de Bellman-Ford est tellement simple qu’il est souvent plus efficace sur des « petits » graphes, jusqu’à quelques milliers de nœuds.

C’est le cœur des protocoles de routages dits « Distance Vector », tels que RIP.

Définissez le concept d'arbre couvrant de poids minimal

Nous avons vu jusqu’ici plusieurs structures arborescentes gérant l’adressage et le routage d’information. Un autre type d’arbre est utile pour la diffusion d’information : l’arbre couvrant de poids minimum.

L'information circule depuis une imprimante, via un serveur, jusqu'à un ordinateur Mac ou PC/Linux.
Diffusion d'une information dans un réseau

Tous ceux que nous avons vu jusqu’ici sont des arbres couvrants.

La diffusion, broadcast en anglais, consiste, pour un nœud, à transmettre à tous les autres nœuds la même information. Par exemple pour annoncer qu’un service est disponible : « l’imprimante est accessible à l’adresse 10.0.42.14 ».

On pourrait faire cela avec |V|-1 communications point à point le long des plus courts chemins, mais la même information va passer plusieurs fois par les mêmes liens et les mêmes nœuds. Cela gâche beaucoup de ressources.

Une autre méthode consiste à ce que chaque nœud, lorsqu’il reçoit l’information, la garde et la retransmette à ses voisins dans un arbre couvrant.

Dès lors, on s’assure qu’il y a uniquement une transmission par arc de l’arbre couvrant et que tous les sommets recevront l’information.

Il y a plusieurs algorithmes d’arbres couvrants de poids minimum. Les plus connus sont celui de Prim et celui de Kruskal qui sont centralisés. Des algorithmes distribués existent mais sont relativement complexes.

La structure d’arbre couvrant de poids minimum (MST pour Minimum Spanning Tree en anglais) est très utilisée, notamment dans l’organisation de l’interconnexion de switchs dans un réseau d’entreprise.

Je vous propose de nous retrouver dans le chapitre suivant pour calculer la capacité d'un réseau.

Exemple de certificat de réussite
Exemple de certificat de réussite