Les algorithmes de Dijkstra et Bellman-Ford

Page Wikipedia de l'algorithme de Dijkstra

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é à l'ensemble grossissant.

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

Voici une implémentation en Python:

    graphe = {
            "A": [("B", 85), ("C", 217), ("E", 173)],
            "B": [("A", 85), ("F", 80)],
            "C": [("A", 217), ("G", 186), ("H", 103)],
            "D": [("H", 183)],
            "E": [("A", 173), ("J", 502)],
            "F": [("B", 80),("I",250)],
            "G": [("C", 186)],
            "H": [("C", 103), ("D",183),("J",167)],
            "I": [("F", 250), ("J", 84)],
            "J": [("E", 502), ("I", 84),("H",167)]
    }   

    def dijkstra(graphe, depart):
        # Retourne un dictionnaire des distances minimales pour tous les sommets accessibles du graphe

        ensemble_grossisant = {depart:0} # Va contenir tous les sommets accessibles et la distance minimale

        distances = {sommet:float('inf') for sommet in graphe}
        distances[depart] = 0 # le premier sommet qui sera sorti l'ensemble des sommets

        while any(distances[s] !=  float('inf') for s in distances):
            choix = min([sommets for sommets in distances], key= lambda x: distances[x])
            print(choix)
            dist_min_ajout = distances.pop(choix) # contient le couple sommet choisi, et distance minimale depuis depart
            ensemble_grossisant[choix] = dist_min_ajout


            # Mise à jour des distances des voisins du choix
            for couple in graphe[choix]:
                voisin, dist_voisin = couple
                if (voisin in distances) and distances[voisin] > dist_min_ajout + dist_voisin:
                    distances[voisin] = dist_min_ajout + dist_voisin

        return ensemble_grossisant

    print(dijkstra(graphe,'A'))

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.

👉 C'est ainsi que les routeurs déterminent la passerelle vers laquelle un paquet doit être envoyé pour atteindre sa destination finale.

Exercice

Adapter le code précédent pour retourner dans l'ensemble grossissant, non plus des couples (sommet, distance optimale) mais des 3-uplets (sommet, distance optimale, voisin d'origine du parcours optimal)

Code à compléter:

def dijkstra(graphe, depart):
    # Retourne un dictionnaire des distances minimales pour tous les sommets accessibles du graphe

    ensemble_grossisant = {depart:(0,depart)} # Va contenir tous les sommets accessibles et la distance minimale

    distances = {sommet:(float('inf'),sommet) for sommet in graphe}
    distances[depart] = (0,depart) # le premier sommet qui sera sorti l'ensemble des sommets

    while any(distances[s][0] !=  float('inf') for s in distances):
        choix = min([sommets for sommets in distances], key= lambda x: distances[x][0])
        dist_min_ajout, voisin_orig = distances.pop(choix) # contient le couple sommet choisi, et distance minimale depuis depart
        ensemble_grossisant[choix] = (...,...) # ajout de la distance trouvée et du voisin qui précède.


        # Mise à jour des distances des voisins du choix
        for couple in graphe[choix]:
            voisin, dist_voisin = couple
            if (voisin in distances) and distances[voisin][0] > ....:
                distances[voisin] = ....

    return ensemble_grossisant

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

{'A': (0, 'A'), 'B': (85, 'A'), 'F': (165, 'B'), 'E': (173, 'A'), 'C': (217, 'A'), 'H': (320, 'C'), 'G': (403, 'C'), 'J': (675, 'E'), 'I': (759, 'J')}

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:

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