TP 4: Algorithmes et compléxité¶
def pgcd(a,b):
if b > a:
a, b = b, a
r = a % b
while r != 0:
a = b
b = r
r = a % b
return b
Voici l'algorithme d'Euclide avec un compteur pour le nombre de division Euclidienne
def pgcd_complexite(a,b):
if b > a:
a, b = b, a
r = a % b
n = 1
while r != 0:
a = b
b = r
r = a % b
n += 1
return n # renvoie le nombre de division Euclidienne effectuée
Pour illustrer la compléxité en terme du nombre de division Euclidienne effectuée on va procéder comme suit:
- On va fixer le nombre de chiffre dans l'écriture de b;
- On va tirer des entiers a et b de manière aléatoire avec la contrainte sur b ci-dessus;
- On va appliquer l'algorithme d'euclide et récupérer le nombre de division;
- Enfin, on fera la moyenne de ces nombres;
- Et on recommence avec un nombre de chiffre dans l'écriture de b plus grand.
Pour tirer des entiers aléatoires, on va faire appelle au module Numpy, et Pyplot pour faire une figure.
from numpy import random as npr
import numpy as np
from matplotlib import pyplot as plt
def moyenne_pgcd_complexite(m, N):
# - m représente le nombre de chiffre maximal
# pour la décomposition de b qu'on va tester
# - N est le nombre de tirage aléatoire avec
# lequels on fera une moyenne des nombres
# de division Euclidienne nécessaire.
res_moy = [] # liste pour enregistrer les résultats
# de compléxité moyenne
# en fonction du nombre de chiffre dans
# la décomposition de b
for i in range(1,m+1):
num_temp = [] # liste pour enregistrer les résultats de compléxité
for _ in range(1,N+1):
b = npr.randint(10**i, 10**(i+1))
# i fixe le nombre de chiffre dans l'écriture de b
a = b + npr.randint(10**3, 10**6)
# on prend a >b avec au moin 3 chiffres en plus et au plus 5.
num_temp.append( pgcd_complexite(a, b) )
res_moy.append( np.mean(num_temp) )
return res_moy
Maintenant, on va faire nos tests.
m = 6
N = 1000
complexite_moy = moyenne_pgcd_complexite(m, N)
n = np.arange(1,m+1)
plt.plot(n, complexite_moy,'ko-', label = 'nbre division')
plt.plot(n, 5*n,'b', label = 'borne théorique')
plt.xlabel("nbre de chiffre dans l'écriture de $b$")
plt.ylabel("nbre de division Euclidienne")
plt.title("Illustration de l'évolution de la compléxité \n \
en fonction du nbre de chiffre dans l'ecriture de $b$")
plt.legend(loc = 'upper left')
plt.show()
On peut aussi illustrer la compléxité temporelle en terme de temps d'éxecution de l'algorithme d'Euclidienne. On va illustrer cette évolution en anticipant la méthode de l'exercice suivant. On va illustrer l'evolution du temps moyen d'éxecution en fonction du nombre de chiffre dans la décomposition de b.
import time # module servant à mesurer le temps d'éxecution d'une commande
def timer_euclide(m, N):
res_moy = [] # liste qui enregistrera les temps moyen d'éxecution
for i in range(m+1): # boucle sur le nombre de chiffre dans l'écriture de b
time_temp = [] # liste qui enregistrera le temps éxecution
# pour un nombre de chiffre donné pour b
for _ in range(1,N+1): # boucle sur le nombre de répétition pour
# une pour un nombre de chiffre donné
b = npr.randint(10**i, 10**(i+1)) # b choisi aléatoirement
a = b + npr.randint(10**3, 10**6) # a aussi en étant plus grand
# que b
start = time.perf_counter() # calcul du temps d'éxecution
pgcd(a, b)
stop = time.perf_counter()
time_temp.append(stop - start)
res_moy.append( np.mean(time_temp) ) # calcul et enregistrement
# du temps moyen d'éxecution
return res_moy
m = 10 # nbre de chiffre maximum dans l'écriture de b
N = 500000 # nombre de répétition
complexite_time_moy = timer_euclide(m, N) # évalution de la compléxité
# temporelle
# illustration
plt.plot(complexite_time_moy,'ko-')
plt.xlabel("nbre de chiffre dans l'écriture de $b$")
plt.ylabel("temps d'éxecution moyen (s)")
plt.title("Illustration de l'évolution du temps d'éxecution \n \
de l'algo d'Euclide en fonction du nbre de chiffre dans l'ecriture de $b$")
plt.show()
2) Implémenter l'algorithme d'Euclide étendu et vérifier son bon fonctionnement sur quelques exemples de votre choix.¶
On remarquera que l'échange de valeur entre x et y
z = x
x = y
y = z
s'écrit tout simplement en Python
x, y = y, x
On peut alors écrire une version plus compacte de l'algorithme d'Euclide étendu.
def Euclide_etendu(a,b):
if b > a:
a, b = b, a
r, u, v = a, 1, 0
r1, u1, v1 = b, 0, 1
while r1 !=0:
q = r // r1
r, r1 = r1, r - q * r1
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
return (r, u, v)
Voici un exemple.
a = 120
b = 23
r, u, v = Euclide_etendu(120, 23)
print("pgcd(%s, %s) = %s" % (a,b,r))
print("%s * %s + %s * %s = %s" % (u, a, v, b, u*a + v * b))
pgcd(120, 23) = 1 -9 * 120 + 47 * 23 = 1
def tri_selection(L):
n = len(L)
for j in range( len(L)-1 ):
ind_min = j
for l in range(j+1, n):
if L[ind_min] > L[l]:
ind_min = l
if ind_min != j:
L[j], L[ind_min] = L[ind_min], L[j]
return L
Testons de bon fonctionnement sur une liste d'entiers tirés aléatoirement.
L = npr.randint(0,100,10)
print(L)
print(tri_selection(L))
[21 80 91 86 45 92 24 85 12 91] [12 21 24 45 80 85 86 91 91 92]
- fonction de tri par insertion
def tri_insertion(L):
n = len(L)
for j in range(1,n):
k, x = j, L[j]
while k > 0 and x < L[k-1]:
L[k] = L[k-1]
k -= 1
L[k] = x
return L
L = npr.randint(0,100,10)
print(L)
tri_selection(L)
print(L)
[13 97 11 13 91 87 8 60 24 47] [ 8 11 13 13 24 47 60 87 91 97]
- fonction de tri rapide
On va décomposer cette fonction en plusieurs sous fonctions. Tout d'abord la fonction qui a un pivot donné fait la partion de la liste en deux sous listes. Ici la fonction modifie la liste entré en argument.
def partition(L, ind_min, ind_max):
ind_pivot = npr.randint(ind_min, ind_max)
L[ind_pivot], L[ind_max] = L[ind_max], L[ind_pivot]
i = ind_min
for j in range(ind_min, ind_max):
if L[j] < L[ind_max]:
L[j], L[i] = L[i], L[j]
i += 1
L[i], L[ind_max] = L[ind_max], L[i]
return i
Ensuite la fonction recursive de tri rapide.
def tri_rapide_rec(L, ind_min, ind_max):
if ind_min < ind_max:
i_pivot = partition(L, ind_min, ind_max)
tri_rapide_rec(L, ind_min, i_pivot - 1)
tri_rapide_rec(L, i_pivot + 1, ind_max)
Enfin la fontion d'éxecution de l'algorithme.
def tri_rapide(L):
tri_rapide_rec(L, 0, len(L)-1 )
On passe aux tests.
L = npr.randint(0,100,10)
print(L)
tri_rapide(L)
print(L)
[21 56 0 29 60 94 23 72 18 65] [ 0 18 21 23 29 56 60 65 72 94]
2) On va illustrer l'évolution du temps de calcul moyen de chacun des algorithmes de tri. Pour cela:¶
a) Créer un fonction timer qui a une liste et une fonction de tri renvoie le temps d'exécution du tri de la liste. Pour cela, on utilisera le module time. Le temps d'exécution sera mesuré de la façon suivante.¶
start = time.perf_counter()
fct_tri(list)
stop = time.perf_counter()
return stop - start
def timer(L,fct_tri):
start = time.perf_counter()
fct_tri(L)
stop = time.perf_counter()
return stop - start
b) Ecrire une fonction Python qui, pour un algorithme de tri donné, génère des listes de nombre aléatoire (de loi qui vous convient) et calculer le temps moyen d'exécution du tri de ces listes.¶
def timer_mean(fct_tri, m, N): # - m taille des listes à trier
# - N le nombre de répétition pour
# une taille de liste donnée
time_temp = []
for _ in range(1,N+1):
L = npr.randint(0, max(1000, m), m) # liste aléatoire de coefficient
# entre 0 et max(1000, m), et de
# taille m
time_exec = timer(L,fct_tri)
time_temp.append(time_exec)
return np.mean(time_temp)
c) Illustrer les vitesses d'exécution moyennes des différents algorithmes en fonction de la taille $n$ des listes considérées.¶
On va créer un fonction qui va générer une liste contenant les temps moyens d'éxecution d'un algo de tri en fonction de la taille de la liste considérée.
def timer_tri(fct_tri, m, N): # - m taille max des listes à trier,
# - N le nombre de répétition pour une taille
# de liste donnée
res_moy = []
for i in range(2, m+1): # la taille minimale des listes est 2
res_moy.append(timer_mean(fct_tri, i, N))
return res_moy
m = 200 # taille max des listes triées
N = 50 # nombre de répétitions pour une taille de liste donnée
# évaluation de la compléxité temporelle
complexite_tri_selec = timer_tri( tri_selection, m, N)
complexite_tri_insert = timer_tri( tri_insertion, m, N)
complexite_tri_rapide = timer_tri( tri_rapide, m, N)
# Illustrations
plt.plot(complexite_tri_selec,'k', label = "tri selection")
plt.plot(complexite_tri_insert ,'b', label = "tri insertion")
plt.plot(complexite_tri_rapide,'r', label = "tri rapide")
plt.xlabel("taille des listes")
plt.ylabel("temps d'éxecution moyen (s)")
plt.title("Illustration de l'évolution du temps d'éxecution \n \
des algos de tri en fonction de la taille des listes")
plt.legend(loc = 'upper left')
plt.show()
Rque: on observe bien le comportement quadratique des algos de tri selection et insertion, ainsi que le comportement quasi-linéaire du tri rapide.
Exercice 3¶
Dans cet exercice on considère l'algorithme de tri fusion dont le principe est le suivant:
- Si le tableau n'a qu'un élément, il est déjà trié.
- Si le tableau a plus d'un élément, séparer le en deux parties de même taille ($\pm1$ élément), et trier ces deux sous tableaux avec l'algorithme de tri fusion (il s'agit de créer une fonction récursive).
- Fusionner les deux tableaux triés en un seul tableau trié.
1) Implémenter l'algorithme de tri fusion.¶
fonction de tri fusion
def tri_fusion(L):
if len(L) <= 1:
return L
else:
n = len(L) // 2
L1 = tri_fusion(L[:n])
L2 = tri_fusion(L[n:])
return fusion(L1, L2)
où fusion opère la fusion des listes.
def fusion(L1, L2):
if len(L1) == 0:
return L2
elif len(L2) == 0:
return L1
else:
if L1[0] <= L2[0]:
return [L1[0]] + fusion(L1[1:],L2) # ici on utilise le type liste
# dont la concatenation se fait
# à l'aide de + (voir TP1)
else:
return [L2[0]] + fusion(L1,L2[1:])
Test de la fonction.
L = npr.randint(0,100,10)
print(L)
print(tri_fusion(list(L)))
[71 98 22 57 45 83 92 16 73 33] [16, 22, 33, 45, 57, 71, 73, 83, 92, 98]
2) Evaluer le temps calcul de cet algorithme en fonction de la taille de la liste et le comparer aux exemples de l'exercice précédent.¶
Pour évaluer la compléxité temporelle (temps calcul), on utilise la fonction timer_tri de l'exercice précédent, avec les mêmes paramètres m et N.
complexite_tri_fusion = timer_tri( tri_fusion, m, N)
Et on compare les résultats obtenus avec ceux des autres fonctions de tri.
plt.plot(complexite_tri_selec,'k', label = "tri selection")
plt.plot(complexite_tri_insert ,'b', label = "tri insertion")
plt.plot(complexite_tri_rapide,'r', label = "tri rapide")
plt.plot(complexite_tri_fusion,'g', label = "tri fusion")
plt.xlabel("taille des listes")
plt.ylabel("temps d'éxecution moyen (s)")
plt.title("Illustration de l'évolution du temps d'éxecution \n \
des algos de tri en fonction de la taille des listes")
plt.legend(loc = 'upper left')
plt.show()
La méthode de tri fusion offre des performances similaires à celles du tri rapide, ce qui confirme le calcul théorique.
3) Déterminer sa compléxité temporelle théorique. On pourra considérer $n$ de la forme $n=2^p$ pour simplifier.¶
Le coût pour trier une liste de taille $n$ se décompose de la façon suivante: $$ t(n) \leq t\Big(\Big[ \frac{n}{2} \Big]\Big) + t\Big(\Big[ \frac{n+1}{2} \Big]\Big) + c\,n$$ où le terme $c\,n$ représente le coût de la fusion des deux tableaux triés, on fait au plus $[n/2]+[(n+1)/2] = n$ comparaisons pour les faire fusionner. Pour simplifier la suite des calculs prenons $n = 2^p$ et posons $s(p)=t(2^p)$. On a alors $$ s(p) \leq 2 s(p-1) + c\,2^p, $$ et en divisant cette inégalité par $2^p$ on obtient $$ x_p \leq x_{p-1} + c,\qquad\text{où}\qquad x_p = \frac{s(p)}{2^p}.$$ Ainsi, $$ x_p = \sum_{k=1}^p x_k - x_{k-1} \leq c\,p $$ avec $x_0 =0$, car on peut estimer que le coût du tri d'une liste de taille 1 est nul (il n'y a rien à trier). Au final, on obtient $x_p \leq c p$, c'est à dire $s(p) \leq c \,p 2^p$, et donc $t(n)=\mathcal{O}(n\ln(n))$.
Exercice 4¶
Dans cet exercice nous allons comparer deux méthodes de recherche: l'algorithme de recherche séquentielle et de recherche dichotomique pour une liste triée.
1) (Algorithme séquentielle) Cet algorithme naïf parcours la liste et teste les éléments un à un. Implémenter cet algorithme en une fonction qui prend en argument la liste et l'élément recherché, puis renvoie la position de cet élément dans la liste s'il si trouve. Déterminer sa compléxité temporelle théorique en "moyenne".¶
Fonction de recherche séquentielle.
def rech_seq(x, L):
n = len(L)
for j in range(n):
if x == L[j]:
return j
else:
j += 1
Pour cet algorithme naïf, consistant à parcourir une liste et à faire une comparaison à chaque étape, on effectue en moyenne $n/2$ comparaisons, et dans le pire des cas $n$. La complexité de cette algorithme est donc $t(n) = \mathcal{O}(n)$ en moyenne et dans le pire des cas.
2) Algorithme dichotomique) Cet algorithme nécessite de travailler avec une liste trié $[a_0,\dots,a_{n-1}]$. Le principe est le suivant:¶
- On compare l'élément recherché $x$ à $a_p$ pour $p=[n/2]$ ($n>1$);
- Si $x=a_p$, $x$ est dans la liste à la place $p$;
- Si $x>a_p$, on cherche $x$ dans la sous liste $[a_{p+1},\dots,a_{n-1}]$ par dichotomie;
- Si $x<a_p$, on cherche $x$ dans la sous liste $[a_0,\dots,a_{p-1}]$ par dichotomie.
Implémenter cet algorithme en une fonction qui prend en argument la liste et l'élément recherché, puis renvoie la position de cet élément dans la liste s'il si trouve. Déterminer la compléxité temporelle théorique de cet algorithme. On pourra considérer $n$ de la forme $n=2^p$ pour simplifier.¶
Fonction de recherche dichotomique.
def rech_dicho_rec(x, L, ind_min, ind_max):
if ind_max > ind_min:
q = (ind_max + ind_min) // 2
y = L[q]
if x == y:
return q
elif x > y:
ind_min = q + 1
return rech_dicho_rec(x, L, ind_min, ind_max)
else:
ind_max = q
return rech_dicho_rec(x, L, ind_min, ind_max)
Fonction d'éxécution de la recherche dichotomique
def rech_dicho(x, L):
return rech_dicho_rec(x, L, 0, len(L))
Testons nos fonctions.
L = range(1,6)
x = npr.randint(1,6)
print(x)
3
rech_seq(x, L)
2
rech_dicho(x, L)
2
Pour la recherche dichotomique (avec une liste triée), consistant à tester le point milieu, et si ce n'est pas l'élément recherché, à poursuivre la recherche dans une des deux sous listes. On a alors la relation $$ t(n) \leq t\Big(\Big[ \frac{n}{2} \Big]\Big)+c.$$ Si on considère des listes de taille $n=2^p$, on a alors $$ t(2^p) \leq t(2^{p-1}) +c.$$ En posant $x_p=t(2^p)$, on obtient la relation $$ x_p \leq x_{p-1} + c,$$ et donc $$ x_p = \sum_{k=1}^p x_k - x_{k-1} +x_0 \leq c \,(p+1) $$ avec $x_0 =c$, car on peut estimer que le coût d'une recherche dans une liste de taille 1 est celui d'une comparaison. Au final, $x_p \leq c \,(p+1)$, c'est à dire $t(2^p) \leq c \,(p+1) $, et donc $t(n)=\mathcal{O}(\ln(n))$.
3) Analyser graphiquement les performances des deux algorithmes de recherche en suivant la demarche des questions $2.a$ et $2.b$ de l'exercice 2¶
Implémentons une fonction timer_rech pour nos deux méthodes
def timer_rech(rech_fct, m, N): # - rech_fct est une fct de recherche
# - m la taille max des listes avec lesquelles
# - N et le nombre de répétition pour calculer
# le temps moyen d'éxecution.
res_moy = []
for i in range(2, m+1):
time_temp = []
for _ in range(1,N+1):
L = npr.randint(0, max(1000, i), i)
x = L[npr.randint(0, i)] # On choisit un point à chercher
# aléatoirement dans la liste
start = time.perf_counter()
if rech_fct == rech_dicho:
L.sort() # Attention pour la recherche dichotomique
# la liste L doit être triée.
# On utilise la méthode sort de python
rech_fct(x, L)
stop = time.perf_counter()
time_temp.append(stop - start)
res_moy.append( np.mean(time_temp) )
return res_moy
m = 700
N = 60
complexite_rech_seq = timer_rech(rech_seq, m, N)
complexite_rech_dicho = timer_rech(rech_dicho,m, N)
plt.plot(complexite_rech_seq,'k', label = "rech_seq")
plt.plot(complexite_rech_dicho ,'b', label = "rech_dicho")
plt.xlabel("taille des listes")
plt.ylabel("temps d'éxecution moyen (s)")
plt.title("Illustration de l'évolution du temps d'éxecution \n \
des algos de recherche en fonction de la taille des listes")
plt.legend(loc = 'upper left')
plt.show()
Exercice 5¶
(Parcours de graphe et distance minimale) Un graphe est un couple $(V,E)$ où $V$ est l'ensemble des sommets du graphe (vertice en anglais) et $E$ l'ensemble des arcs reliant les différents sommets (edge en anglais). On dit qu'un graphe est orienté si les arcs sont orientés: aller du sommet $i$ au sommet $j$ n'a pas le mêm sens que d'aller de $j$ à $i$.
A un graphe on peut associer une matrice d'adjacence $A=(a_{jl})_{(j,l)\in E\times E}$ dont les coefficients sont les poids des arcs reliant les différents sommets. Si un coefficient de cette matrice est nul, c'est qu'il n'y a pas d'arcs entre les deux sommets dans le sens considéré. Pour un graphe orienté, la matrice d'adjacence n'est pas symmétrique.
En pratique, on peut représenter un graphe à l'aide d'un dictionnaire. Par exemple,
G = {
'a': {'b': 1 },
'b': {'a': 2, 'c': 3 },
'c': {'d': 3, 'e': 4 },
'd': {'b': 1 },
'e': { }
}
1) Implémenter l'algorithme de parcours en largeur d'un graphe que vous trouverez à l'adresse https://fr.wikipedia.org/wiki/Algorithme\_de\_parcours\_en\_largeur. On commencera par considérer l'exemple de graphe proposé par Wikipedia.¶
On commence par rentrer le graphe.
G = {
'a': {'b':1, 'c':1, 'e':1},
'b': {'d':1, 'f':1},
'c': {'g':1},
'd': {},
'e': {'f':1},
'f': {},
'g': {},
}
def parcours_largeur(G):
noeuds = list(G.keys())
for x in G.keys():
if x in noeuds:
print(x)
noeuds.remove(x)
for d in G[x].keys():
if d in noeuds:
print(d)
noeuds.remove(d)
On peut tester notre fonction sur le graphe $G$
parcours_largeur(G)
a b c e d f g
2) Puis de parcours en profondeur que vous trouverez à l'adresse https://fr.wikipedia.org/wiki/Algorithme\_de\_parcours\_en\_profondeur.¶
def parcours_sommet(sommet, G, Sommets):
if sommet in Sommets:
print(sommet)
Sommets.remove(sommet)
D = G[sommet]
if type(D) == dict:
for voisin in D.keys():
Sommets = parcours_sommet(voisin, G, Sommets)
return Sommets
def parcours_profondeur(G, Sommets):
for x in G.keys():
if x in Sommets:
Sommets = parcours_sommet(x, G, Sommets)
On peut tester notre fonction sur le graphe $G$.
Sommets = list(G.keys())
parcours_profondeur(G, Sommets)
a b d f c g e
On peut aussi parcourir le graphe de la question suivante.
G = {
'a': {'b':4, 'c':2},
'b': {'a':4, 'd':5, 'c':1},
'c': {'a':2, 'b':1, 'd':8, 'e':10},
'd': {'b':5, 'c':8, 'e':2},
'e': {'c':10, 'd':2, 'f':3},
'f': {'e':3, 'd':6},
}
parcours_largeur(G)
a b c d e f
Sommets = list(G.keys())
parcours_profondeur(G, Sommets)
a b d c e f
3) Dans la suite, on va s'intéresser à la distance d'un sommet particulier (qu'on appelle la source et qu'on note $s$) aux autres sommets du graphe. Pour se faire on va utiliser l'algorithme de Bellman-Ford qu'on appliquera sur le graphe suivant:¶
G = {
'a': {'b': 4, 'c':2 },
'b': {'a': 4, 'c': 1, 'd': 5 },
'c': {'a': 2, 'b': 1, 'd': 8, 'e': 10 },
'd': {'b': 5, 'c': 8, 'e': 2 },
'e': {'c': 10, 'd': 2, 'f': 3 },
'f': {'e': 3, 'd': 6 }
}
a) Ecrire une fonction qui décompose un graphe $G$ de la forme ci-dessus en un couple $(V,E)$ où $V$ est une liste de sommet et $E$ un dictionnaire dont les clés sont les arcs et les valeurs sont les poids de chaque arc.¶
V = list(G.keys())
E = {}
for x in G.keys():
for y in G[x].keys():
E.update({(x,y):G[x][y]})
b)¶
On note $\pi(v)$ la distance de la source au sommet $v$.
On commence l'algorithme par l'initialisation $\pi(s)\leftarrow 0$ et $\pi \leftarrow +\infty$. Pour implémenter cette seconde condition, on pourra utiliser la commande \texttt{float('inf')}.
L'idée de l'algorithme est que pour tout sommet $v$, si passer par un des prédécessurs $u$ de $v$ raccourcit la distance, alors on remplace $\pi(v)$ par $\pi(u)+a_{u\,v}$, où on rapplle que $a_{u\,v}$ est la pondération de l'arc $(u,v)$.
L'algorithme de Bellman-Ford est le suivant:
$\pi(s) \leftarrow 0$
Pour tous les sommets $v\neq s$ du graphe
$\pi(v)\leftarrow +\infty$
Tant que $\pi$ change faire
Pour chaque arc $(u,v)\in E$ du graphe faire}
Si $\pi(v) > \pi(u) + a_{u\,v}$ faire
$\pi(v) \leftarrow \pi(u)+ a_{u\,v}$
retourner $\pi$
Calcul la distance minimale d'un poitn source aux autres points du graphe.
Implémenter cet algorithme et calculer la distance des sommets de $G$ à a, b,.... On pourra essayer d'autre graphe.¶
def distance(s, V, E):
pi = {v: float('inf') for v in V}
pi[s] = 0
pi0 = {}
while pi!=pi0:
pi0 = pi.copy()
for u,v in E.keys():
if pi[v] > pi[u] + E[(u,v)]:
pi[v] = pi[u] + E[(u,v)]
# on peut enlever la distance de s dont on sait qu'elle vaut 0
pi.pop(s)
return pi
Un exemple pour 'a' comme point source.
distance('a', V, E)
{'b': 3, 'c': 2, 'd': 8, 'e': 10, 'f': 13}
Calcul des distances des tous les points du graphe.
dist = {}
for s in V:
dist.update({s: distance(s, V, E)})
On regarde les distances pour chaque point.
for s in V:
print('distance de %s = %s' % (s, dist[s]))
distance de a = {'b': 3, 'c': 2, 'd': 8, 'e': 10, 'f': 13}
distance de b = {'a': 3, 'c': 1, 'd': 5, 'e': 7, 'f': 10}
distance de c = {'a': 2, 'b': 1, 'd': 6, 'e': 8, 'f': 11}
distance de d = {'a': 8, 'b': 5, 'c': 6, 'e': 2, 'f': 5}
distance de e = {'a': 10, 'b': 7, 'c': 8, 'd': 2, 'f': 3}
distance de f = {'a': 13, 'b': 10, 'c': 11, 'd': 5, 'e': 3}