Reprenons le graphe suivant dans lequel nous souhaitons déterminer le parcours le plus court menant du sommet A au sommet G.
Une autre possibilité pour représenter un graphe avec Python est d'utiliser une matrice (ou liste bidimensionnelle). Cela revient en fait à construire sa matrice d'adjacence, c'est-à-dire la matrice dont le coefficient \( a_{ij} \) est égal à la pondération de l'arête menant du sommet \( i \) au sommet \( j \).
Dans ces conditions les sommets ne seront plus repérés par leur nom mais par un nombre compris entre \( 0 \) et \( n-1 \), où \( n \) est l'ordre du graphe. Il faut donc préalablement décider d'une convention d'association entre le nom du sommet et son numéro dans la matrice. Quand c'est possible, l'ordre alphabétique est privilégié.
Proposition d'un script
Ce script met en oeuvre l'algorithme de Moore-Dijkstra en donnant la longueur de chacun des chemins issus du sommet A et allant vers les autres sommets
def moore_dijkstra_2 (M, s):
inf = sum(sum(ligne) for ligne in M) + 1
nb_sommets = len(M)
s_explore = {s : [0, [s]]}
#On associe au sommet d'origine s la liste [longueur, plus court chemin]
s_a_explorer = {j : [inf, ""] for j in range(nb_sommets) if j != s}
#On associe à chaque sommet j à explorer la liste [longueur, sommet précédent]
for suivant in range(nb_sommets):
if M[s][suivant]:
s_a_explorer[suivant] = [M[s][suivant], s]
print("Dans le graphe d\'origine {} de matrice d\'adjacence :".format(s))
for ligne in M:
print(ligne)
print()
print("Plus courts chemins de")
while s_a_explorer and any(s_a_explorer[k][0] < inf for k in s_a_explorer):
s_min = min(s_a_explorer, key = s_a_explorer.get)
longueur_s_min, precedent_s_min = s_a_explorer[s_min]
for successeur in range(nb_sommets):
if M[s_min][successeur] and successeur in s_a_explorer:
dist = longueur_s_min + M[s_min][successeur]
if dist < s_a_explorer[successeur][0]:
s_a_explorer[successeur] = [dist, s_min]
s_explore[s_min] = [longueur_s_min, s_explore[precedent_s_min][1] + [s_min]]
del s_a_explorer[s_min]
print("longueur", longueur_s_min, ":", " -> ".join(map(str, s_explore[s_min][1])))
for k in s_a_explorer:
print("Il n\'y a pas de chemin de {} à {}".format(s, k))
return s_explore
maMatrice = [[0, 2, 1, 0, 0, 0, 0],
[2, 0, 2, 1, 3, 0, 0],
[1, 2, 0, 4, 3, 5, 0],
[0, 1, 4, 0, 3, 6, 5],
[0, 3, 3, 3, 0, 1, 0],
[0, 0, 5, 6, 1, 0, 2],
[0, 0, 0, 5, 0, 2, 0]]
moore_dijkstra_2(maMatrice, 0)
Pour s'entraîner
- Modifier le script ci-dessus pour faire afficher le sommet sélectionné, le plus court chemin depuis le sommet d'entrée ainsi que les dictionnaires
s_exploreets_a_explorerà chaque tour de la bouclewhile. Cela permettra de se rendre compte de l'évolution de ces deux listes au cours du processus.- Piste ?
- Solution ?
Insérer des fonctions
printau bon endroit.def moore_dijkstra_2 (M, s): inf = sum(sum(ligne) for ligne in M) + 1 nb_sommets = len(M) s_explore = {s : [0, [s]]} #On associe au sommet d'origine s la liste [longueur, plus court chemin] s_a_explorer = {j : [inf, ""] for j in range(nb_sommets) if j != s} #On associe à chaque sommet j à explorer la liste [longueur, sommet précédent] for suivant in range(nb_sommets): if M[s][suivant]: s_a_explorer[suivant] = [M[s][suivant], s] print("Dans le graphe d\'origine {} de matrice d\'adjacence :".format(s)) for ligne in M: print(ligne) print() while s_a_explorer and any(s_a_explorer[k][0] < inf for k in s_a_explorer): s_min = min(s_a_explorer, key = s_a_explorer.get) longueur_s_min, precedent_s_min = s_a_explorer[s_min] for successeur in range(nb_sommets): if M[s_min][successeur] and successeur in s_a_explorer: dist = longueur_s_min + M[s_min][successeur] if dist < s_a_explorer[successeur][0]: s_a_explorer[successeur] = [dist, s_min] s_explore[s_min] = [longueur_s_min, s_explore[precedent_s_min][1] + [s_min]] del s_a_explorer[s_min] print() print("On a sélectionné le sommet {}".format(s_min)) print("Plus courts chemins de longueur", longueur_s_min, ":", " -> ".join(map(str, s_explore[s_min][1]))) print("La nouvelle liste des sommets explorés est : ") print(s_explore) print("La nouvelle liste des sommets à explorer est : ") print(s_a_explorer) print() for k in s_a_explorer: print("Il n\'y a pas de chemin de {} à {}".format(s, k)) return s_explore maMatrice = [[0, 2, 1, 0, 0, 0, 0], [2, 0, 2, 1, 3, 0, 0], [1, 2, 0, 4, 3, 5, 0], [0, 1, 4, 0, 3, 6, 5], [0, 3, 3, 3, 0, 1, 0], [0, 0, 5, 6, 1, 0, 2], [0, 0, 0, 5, 0, 2, 0]] moore_dijkstra_2(maMatrice, 0) - Modifier le script ci-dessus pour laisser à l'utilisateur le choix du sommet d'entrée et du sommet de sortie et pour obtenir le plus court chemin entre ces deux sommets.
On veillera à structurer le script convenablement.
- Piste ?
- Solution ?
Ajouter une fonction
entree_sortieprenant en argument le graphe, le sommet d'entrée et le sommet de sortie choisis par l'utilisateur.#---FONCTION QUI CALCULE TOUS LES PLUS COURTS CHEMINS DE L'ENTREE A CHACUN DES SOMMETS------- def moore_dijkstra_1(G, s): inf = sum(sum(G[sommet][i] for i in G[sommet]) for sommet in G) + 1 #On considère comme "infini" un majorant de la somme de toutes les #pondérations du graphe global s_explore global s_a_explorer s_explore = {s : [0, [s]]} #On associe au sommet d'origine s la liste [longueur, plus court chemin] s_a_explorer = {j : [inf, ""] for j in G if j != s} #On associe à chaque sommet j à explorer la liste [longueur, sommet précédent] for suivant in G[s]: s_a_explorer[suivant] = [G[s][suivant], s] print("Dans le graphe d\'origine {} dont les arcs sont :".format(s)) for k in G: print(k, ":", G[k]) print() #On créé une boucle qui tourne tant que la liste des sommets à explorer contient #des points tels que la longueur provisoire calculée depuis l'origine est #inférieure à l'infini while s_a_explorer and any(s_a_explorer[k][0] < inf for k in s_a_explorer): s_min = min(s_a_explorer, key = s_a_explorer.get) longueur_s_min, precedent_s_min = s_a_explorer[s_min] for successeur in G[s_min]: if successeur in s_a_explorer: dist = longueur_s_min + G[s_min][successeur] if dist < s_a_explorer[successeur][0]: s_a_explorer[successeur] = [dist, s_min] s_explore[s_min] = [longueur_s_min, s_explore[precedent_s_min][1] + [s_min]] del s_a_explorer[s_min] return s_explore #---------------------FONCTION QUI DEMANDE L'ENTREE ET LA SORTIE DU GRAPHE------------------ def entree_sortie(M, entree, sortie): moore_dijkstra_2(M, entree) for k in s_explore: if sortie == k: print("Le plus court chemin menant de {} à {} est {} ".format(entree, sortie, s_explore[k][1])) print("Son poids est égal à {}".format(s_explore[k][0])) for k in s_a_explorer: if sortie == k: print("Il n\'existe aucun chemin de {} à {}".format(entree, sortie)) #-------------------------------------------PROGRAMME PRINCIPAL------------------------------ MonGraphe = { 'A':{'B':2, 'C':1}, 'B':{'A':2, 'C':2, 'D':1, 'E':3}, 'C':{'A':1, 'B':2, 'D':4, 'E':3, 'F':5}, 'D':{'B':1, 'C':4, 'E':3, 'F':6, 'G':5}, 'E':{'B':3, 'C':3, 'D':3, 'F':1}, 'F':{'C':5, 'D':6, 'E':1, 'G':2}, 'G':{'D':5, 'F':2} } entree = input("Quel est votre sommet d'entrée ? ") sortie = input("Quel est votre sommet de sortie ? ") print() entree_sortie(MonGraphe, entree, sortie)