TP3 - Algorithme de Dijkstra

Définition de la classe Graphe

Dans ce TP, nous allons utiliser une classe Graphe définie par un dictionnaire. La clé est un sommet et la valeur est une liste de tuples (voisin, poids) représentant les sommets adjacents et le poids de l'arête.

class Graphe:
    """classe graphe définie par un dictionnaire formé par : sommets : [(liste d'adjacence, poids)]"""
    def __init__(self,graphe):
        self.graphe = graphe
Par exemple, le graphe :
Graphe pondéré exemple

sera défini par :

G = Graphe({
    'A':[('B',2),('C',4),('D',6)],
    'B':[('A',2),('C',4)],
    'C':[('A',4),('B',4),('D',1),('E',5)],
    'D':[('A',6),('C',1),('E',2)],
    'E':[('D',2),('C',5)]
})

Exercices

  1. Compléter la classe Graphe avec les méthodes liste_voisins et liste_sommets qui retournent respectivement la liste des sommets adjacents (ou voisins) à un sommet donné et la liste de tous les sommets du graphe.

  2. En utilisant l'algorithme en pseudo-code ci-dessous, écrire une fonction dico_dijkstra(graphe,sommet) qui prend en paramètres 1 graphe et 1 sommet de ce graphe et qui retourne un dictionnaire dont les clés sont les sommets du graphe et les valeurs sont formées par le couple (parent, poids).

#fonction qui retourne un dictionnaire dont les clés sont les sommets et les valeurs sont (poids, parent)
fonction dico_dijkstra(graphe,sommet){
    sommets_select = []  #sommets déjà selectionnés
    poids_total = 0
    dictionnaire_D = dictionnaire {clés : tous les sommets / valeurs : (+oo, None)} 
                    # valeurs = couple(poids, parent), +oo = float(inf) en Python 
    Mettre à (0, None) la clé sommet dans dictionnaire_D
    Tant que le nombre de sommets sélectionnés est différent du nombre total de sommets {
        s = sommet ayant le + petit poids dans dictionnaire_D et qui n''est pas dans sommets_select  
            #vous pouvez faire une fonction pour déterminer ce sommet
        poids_total = dpoids de s
        placer s dans sommets_select
        v = liste des voisins de s qui ne sont pas déjà sélectionnés #liste formé des tuples (sommet, poids)
        Pour i et j dans v {  #i=sommet j=poids du sommet
            si poids_total + j < poids du sommet {
                poids du sommet = poids_total + j  #dans le dictionnaire_D,
                                                   #on remplace le poids du sommet par poids_total + j
                parent = s                         # et on remplace le parent par s
                }
        }
    return dictionnaire_D 
    }

Exemple : Pour le graphe G précédent dico_dijkstra(G,'A') doit retourner : {'A': [0, None], 'B': [2, 'A'], 'C': [4, 'A'], 'D': [5, 'C'], 'E': [7, 'D']}

  1. Écrire la fonction dijkstra(graphe,start,end) qui prend en paramètre un graphe, un sommet de départ (start) et un sommet d'arrivé (end) et qui retourne le chemin de poids minimum entre ces 2 sommets sous la forme d'une liste et le poids total.

  2. Application : Le graphe ci-dessous représente le plan d'une ville.

    Le sommet A désigne l'emplacement des services techniques.

    Les sommets B, C, D, E, F et G désignent les emplacements de jardins publics. Une arête représente l'avenue reliant deux emplacements et est pondérée par le nombre de feux tricolores situés sur le trajet.

    Plan de ville avec graphe pondéré

    En utilisant l'algorithme de Dijkstra, déterminer un trajet comportant un minimum de feux tricolores reliant A à G.

    réponse : (['A', 'C', 'E', 'F', 'G'], 7)