Considérons le graphe suivant dans lequel nous souhaitons déterminer le parcours le plus court menant du sommet A au sommet G.

Une possibilité pour représenter un graphe avec Python est d'utiliser un dictionnaire qui, à chaque sommet, associe un sous-dictionnaire composé de ses sommets adjacents associés à la pondération de l'arête incidente:

Graphe = {
	'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}
	}

Ainsi Graphe['A']['B'] est le poids de l'arête incidente à A et B.

Le parcours d'une telle structure permet de remplir ou vider deux dictionnaires. Le premier qui se remplira au fur et à mesure contiendra les sommets explorés (s_explore) et le second qui se videra au fur et à mesure contiendra les sommets à explorer (s_a_explorer).

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_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
    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()
    print("Plus courts chemin de")
    
    #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]
        print("longueur", longueur_s_min, ":", " -> ".join(s_explore[s_min][1]))
        
    for k in s_a_explorer:
        print("Il n\'y a aucun chemin de {} à {}".format(s, k))
    print()
    
    return s_explore
    
    
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}
    }
        
moore_dijkstra_1(MonGraphe, 'A')
	

Pour s'entraîner

1. 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_explore et s_a_explorer à chaque tour de la boucle while. Cela permettra de se rendre compte de l'évolution de ces deux listes au cours du processus.
   • Piste ?
   • Solution ?

   Insérer des fonctions print au bon endroit.

   
   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
       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()
       print("Le sommet de départ est {}".format(s))
       print()
       print("La liste des sommets à explorer est : ")
       print(s_a_explorer)
       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]
           print()
           print("On a sélectionné le sommet {}".format(s_min))
           print("Plus courts chemin de longueur", longueur_s_min, ":", " -> ".join(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 aucun chemin de {} à {}".format(s, k))
       print()
       
       return s_explore
       
       
   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}
       }
           
   moore_dijkstra_1(MonGraphe, 'A')
   						




2. Reprendre le script initial et le modifier 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 avec des fonctions en séparant les calculs des affichages.
   • Piste ?
   • Solution ?

   Ajouter une fonction affichage prenant en argument le graphe, le sommet d'entrée et le sommet de sortie choisis par l'utilisateur.

   
   def moore_dijkstra_1(G, s):
       """
        FONCTION QUI CALCULE TOUS LES PLUS COURTS CHEMINS DE L'ENTREE A CHACUN DES SOMMETS
       """
       inf = sum(sum(G[sommet][i] for i in G[sommet]) for sommet in G) + 1
       global s_explore
       global s_a_explorer
       s_explore = {s : [0, [s]]}
       s_a_explorer = {j : [inf, ""] for j in G if j != s}
       for suivant in G[s]:
           s_a_explorer[suivant] = [G[s][suivant], s]
       
       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
   
   
    
   
   def affichage(G, entree, sortie):
       """
       FONCTION D'AFFICHAGE DU PLUS COURT CHEMIN ENTRE L'ENTREE ET LA SORTIE DU GRAPHE
       """
       moore_dijkstra_1(G, entree)
       
       print("Dans le graphe d\'origine {} dont les arcs sont :".format(entree))
       for k in MonGraphe:
           print(k, ":", MonGraphe[k])
       print()
       
       for k in s_explore:
           if sortie == k:
               print("Le plus court chemin menant de {} à {} est ".format(entree, sortie), end="")
               print("->".join(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))
   
       
   #---------------------------------UTILISATION -----------------------------
   
   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()
   affichage(MonGraphe, entree, sortie)
   						




3. Modifier le script ci-dessus pour laisser à l'utilisateur la possibilité de saisir son propre graphe avec un retour systématique du programme en cas d'erreur de saisie (par exemple si l'utilisateur saisit une chaîne de caractère au lieu d'un entier, le programme devra permettre de corriger la saisie).
   • Piste ?
   • Solution ?

   Ajouter une fonction saisie_graphe prenant en argument le nombre de sommets. Utiliser la structure Try Except pour la gestion des erreurs.

   
     
   def saisie_graphe(n):
       """
       FONCTION QUI PERMET LA SAISIE D'UN GRAPHE
       """
       global MonGraphe
       MonGraphe = {}
       list_sommets = []
   
       for i in range(n):
           adjacents = {}
           nb_liens = []
           s_adj = []
           poids = []
           sommet = input("Nom de votre {}ème sommet : ".format(i+1))
           list_sommets.append(sommet)
           test0 = 1
           while test0==1:
               try:
                   lien = int(input("Combien de sommets sont adjacents à {} ? ".format(list_sommets[i])))
                   test0 = 0
               except ValueError:
                   print("Ce n'est pas un nombre entier. Veuillez recommencer.")
           nb_liens.append(lien)
       
           for j in range(lien):
               adjacent = input("Nom du {}ème sommet adjacent à {} : ".format(j+1, list_sommets[i]))
               s_adj.append(adjacent)
               test1 = 1
               while test1==1:
                   try:
                       p = float(input("Quel est le poids de l'arête {}-{} ? ".format(list_sommets[i], adjacent)))
                       test1 = 0
                   except ValueError:
                       print("Ce n'est pas un nombre entier. Veuillez recommencer.")
               poids.append(p)
           for k in range(lien):
               adjacents[s_adj[k]] = poids[k]
           MonGraphe[list_sommets[i]] = adjacents
           
       return MonGraphe
   
   
   
     
   
   def moore_dijkstra_1(G, s):
       """
       FONCTION QUI CALCULE TOUS LES PLUS COURTS CHEMINS DE L'ENTREE A CHACUN DES SOMMETS
       """
       inf = sum(sum(G[sommet][i] for i in G[sommet]) for sommet in G) + 1
       global s_explore
       global s_a_explorer
       s_explore = {s : [0, [s]]}
       s_a_explorer = {j : [inf, ""] for j in G if j != s}
       for suivant in G[s]:
           s_a_explorer[suivant] = [G[s][suivant], s]
    
       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
   
   
   
   
     
   
   def affichage(G, entree, sortie):
       """
       FONCTION D'AFFICHAGE DU PLUS COURT CHEMIN ENTRE L'ENTREE ET LA SORTIE DU GRAPHE
       """
       moore_dijkstra_1(G, entree)
   
       print("Dans le graphe d\'origine {} dont les arcs sont :".format(entree))
       for k in MonGraphe:
           print(k, ":", MonGraphe[k])
       print()
       
       for k in s_explore:
           if sortie == k:
               print("Le plus court chemin menant de {} à {} est ".format(entree, sortie), end="")
               print("->".join(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))
   
       
   
   
   #-------------------------------------------UTILISATION------------------------------
   
   test = 1
   while test == 1:
       try:
           n = int(input("Quel est l'ordre de votre graphe ? "))
           test = 0
       except ValueError:
           print("Ce n'est pas un entier. Veuillez recommencer.")
   saisie_graphe(n)
   entree = input("Quel est votre sommet d'entrée ? ")
   sortie = input("Quel est votre sommet de sortie ? ")
   print()
   affichage(MonGraphe, entree, sortie)
   						

On propose une version un peu nettoyée (séparation des calculs et des affichages, principe à respecter dans vos scripts):

from math import inf

Graphe = {
	'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}
	}



def mini(listeSommets, marque):
	"""
	Renvoie le sommet de listeSommets
	ayant la plus petite marque.
	"""
	marquePlusPetite = inf
	for s in listeSommets:
		if marque[s] < marquePlusPetite:
			marquePlusPetite = marque[s]
			sommetPlusPetit = s
	return sommetPlusPetit
	
	
def dijkstra(graphe, depart, arrivee):
	
	# initialisation
	marque = {}
	for sommet in graphe: marque[sommet] = inf
	marque[depart] = 0
	
	non_selectionnes = [sommet for sommet in graphe]
	 
	pere = {}
	pere[depart] = None
	
	# boucle principale:
	while non_selectionnes:
		# sélection:
		s = mini(non_selectionnes, marque)
		if s == arrivee: break
		non_selectionnes.remove(s)
		
		# mise à jour des voisins du sommet sélectionné:
		VoisinsAVisiter = [sommet for sommet in graphe[s] if sommet in non_selectionnes]
		for sommet in VoisinsAVisiter:
			p = marque[s] + graphe[s][sommet] 
			if p < marque[sommet]:
				marque[sommet] = p
				pere[sommet] = s
	
	return marque, pere
	 
	
def affichageCheminMin(graphe, depart, arrivee):
	distance, pere = dijkstra(Graphe, depart, arrivee)
	print("La distance de {} à {} est de longueur {}.".format(depart, arrivee, distance[arrivee]))
	chemin = arrivee
	sommet = arrivee
	while pere[sommet] != None:
		chemin = pere[sommet] + chemin
		sommet = pere[sommet]
	print()
	print("Le chemin de {} à {}: {}.".format(depart, arrivee,chemin))
 

affichageCheminMin(Graphe, 'A', 'G')