Les plus courts chemins dans un graphe

Les questions sur la connexité dans un graphe et sur le nombre de chaînes (resp. chemins) reliant deux sommets dans un graphe non orienté (reso. orienté) sont souvent accompagnés des questions de plus court chemin.

Dans un graphe pondéré, quel est le plus court chemin reliant un sommet A à un sommet B ?

Plusieurs algorithmes célèbres répondent à cette question.

Algorithme de Dijkstra⚓︎

Sans doute le plus célèbre.

Il est utilisé par de nombreux routeurs pour rendre le routage plus efficace.

Page Wikipedia de l'algorithme de Dijkstra

Principe⚓︎

Pour trouver les routes les plus courtes depuis A vers tous les autres sommets (ou ville dans la version originale de Dijkstra), nous choisissons à chaque tour de boucle while:

la ville non encore choisie qui a la plus courte distance depuis A

et nous mettons à jour toutes les distances qui sont diminuées en passant par une route depuis la ville choisie.

Ainsi à chaque tour de boucle, un sommet/ville est ajouté avec sa distance minimale depuis A à l'ensemble grossissant.

La boucle continue jusqu'à épuisement des sommets/ villes.

Voici une implémentation en Python à compléter:

Trouver par quel chemin passer...⚓︎

L'algorithme précédent permet de déterminer les distances minimales depuis un sommet (ou une ville) donné, à condition que les poids des arêtes soient positifs.

Cependant, pour qu'il soit utilisable dans un système de routage (comme sur Internet), il manque une information essentielle : le chemin parcouru pour atteindre la destination.

Pour remédier à cela, nous allons adapter l'algorithme afin que chaque sommet ajouté à l'ensemble des distances minimales soit associé au sommet précédent depuis lequel cette distance minimale a été trouvée.

Ainsi, en remontant les sommets (ou villes) du parcours optimal, nous pourrons retrouver l'itinéraire exact emprunté depuis la ville de départ.

👉 Commr évoqué plus haut, c'est ainsi que les routeurs déterminent la passerelle vers laquelle un paquet doit être envoyé pour atteindre sa destination finale.

Dijkstra avec un retour qui permet de trouver le chemin le plus court et pas seulement la valeur de la distance

Le résultat à trouver avec le graphe en exemple est :

Python
>>>dijkstra(graphe, 'A')
{   'A': (0, 'A'),
    'B': (85, 'A'),
    'F': (165, 'B'),
    'E': (173, 'A'),
    'C': (217, 'A'),
    'H': (320, 'C'),
    'G': (403, 'C'),
    'I': (415, 'F'),
    'J': (487, 'H'), 
    'D': (503, 'H')}

Algorithme de Bellman-Ford⚓︎

L'algorithme de Bellman-Ford calcule, étant donnés un graphe sans cycle de poids négatif et un sommet source (depart), un plus court chemin de depart à chaque sommet de graphe.

Pour cela, il détermnine à chaque tour de boucle si une arête permet de diminuer (relaxer) une distance entre deux sommets:

Exercice⚓︎

Complète le code:

Python
def BellmanFord(graphe, depart):
    distances = {sommet:float('inf') for sommet in graphe}
    distances[depart] = 0

    # Répétition de la boucle autant de fois qu'il y'a de sommets moins 1
    for _ in range(...):

        # Parcours de toutes les arêtes    
        for sommet in graphe:
            for voisin, dist_voisin in graphe[sommet]:
                if distances[voisin] > ...:

            ...

    return distances