Dijsktra : correction à la main et en python

Il fallait pour aujourd’hui déterminer le plus court chemin de H à E dans ce graphe pondéré à l’aide de l’algorithme de Dijkstra.

À la main

On corrige avec notre maintenant habituel tableau :

En python ?

Le fruit du travail de TP hier, groupe Alanis, Axel et Bastien :

On marque la sélection H avec poids 0
Pour B, on remplace (None, 1000) par ('H', 12)
Pour C, on remplace (None, 1000) par ('H', 20)
Pour D, on remplace (None, 1000) par ('H', 9)
On marque la sélection D avec poids 9
Pour C, on remplace ('H', 20) par ('D', 17)
Pour F, on remplace (None, 1000) par ('D', 30)
On marque la sélection B avec poids 12
Pour G, on remplace (None, 1000) par ('B', 25)
On marque la sélection C avec poids 17
Pour F, on remplace ('D', 30) par ('C', 28)
Pour G, on remplace ('B', 25) par ('C', 24)
On marque la sélection G avec poids 24
Pour E, on remplace (None, 1000) par ('G', 33)
On marque la sélection F avec poids 28
Pour E, on remplace ('G', 33) par ('F', 31)
On marque la sélection E avec poids 31

***********
* Bilan : *
***********

Le parcours le plus court a pour longueur 31
Par exemple : 'H', 'D', 'C', 'F', 'E'

Le code pour implémenter un graphe pondéré et la fonction dijkstra en cliquant sur « lire la suite ». Bravo à ces trois codeurs !

# Dictionnaire représentant un arbre pondéré à l'aide de couples
g = {'B': [('G', 13), ('H', 12)],
     'C': [('D', 8), ('F', 11), ('G', 7), ('H', 20)],
     'D': [('C', 8), ('F', 21), ('H', 9)],
     'E': [('F', 3), ('G', 9)],
     'F': [('C', 11), ('D', 21), ('E', 3), ('G', 5)],
     'G': [('B', 13), ('C', 7), ('E', 9), ('F', 5)],
     'H': [('B', 12), ('C', 20), ('D', 9)]}


def dijkstra(g, entree, sortie, infini=2 ** 30):
    marques = []  # Contiendra le nom des sommets visités

    # Distance minimale trouvée pour chaque valeur dès le départ
    distances = {sommet: (None, infini) for sommet in g}
    #     Sommet d'origine (None par défaut), distance

    distances[entree] = 0  # On initialise la distance du départ

    # Nombre de sommets du graphe, longueur du dictionnaire
    taille_graph = len(g)

    selection = entree
    coefficient = 0

    while len(marques) < taille_graph:
        # On marque la 'selection'
        marques.append(selection)
        print(f"On marque la sélection {selection} avec poids {coefficient}")
        # On parcours les voisins de 'selection'
        for voisin in g[selection]:
            # voisin est le couple (sommet, poids de l'arête)

            sommet = voisin[0]  # Le sommet qu'on, parcours
            poids = voisin[1]  # Le poids de selection au sommet
            if sommet not in marques:
                # Pour chaque voisin non marqué,
                # on compare coefficient + arête
                # avec la distance du dictionnaire
                d = distances[sommet][1]
                if coefficient + poids < d:
                    # Si c'est plus petit, on remplace
                    print(f"Pour {sommet}, on remplace {distances[sommet]}", end='')
                    print(f" par {(selection, coefficient + poids)}")
                    distances[sommet] = (selection, coefficient + poids)

        # On recherche le minimum parmi les non marqués
        minimum = (None, infini)
        for sommet in g:
            if sommet not in marques and distances[sommet][1] < minimum[1]:
                minimum = (sommet, distances[sommet][1])

        # puis il devient notre nouvelle 'selection'
        selection, coefficient = minimum

    sommet = sortie
    parcours = [sortie]
    longueur = distances[sortie][1]
    # On parcours le graphe à l'envers pour obtenir le chemin
    while sommet != entree:
        sommet = distances[sommet][0]
        parcours.append(sommet)
    parcours.reverse()

    # On renvoie le chemin le plus court et la longueur
    return parcours, longueur


parcours, longueur = dijkstra(g, 'H', 'E', 1000)
print("\n***********\n* Bilan : *\n***********\n")
print("Le parcours le plus court a pour longueur", longueur)
print("Par exemple :", str(parcours)[1: -1])

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.