1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
G= {
'a':{ 'b':1.54 , 'c':2.97} ,
'b':{ 'a':1.54 , 'f':5 , 'c':10.5} ,
'c':{ 'a':2.97 , 'b':10.5 , 'f':2.33 , 'e':4.25} ,
'd':{ 'f':8.01,'e':3.73 } ,
'e':{ 'c':4.25 , 'd':3.73} ,
'f':{ 'b':5 , 'c':2.33 , 'd':8.01}
}
def graphprim(G):
F=priority_dict()
for u in G:F[u]=float('inf')
s=premiersommet(G)
F[s]=0
pere[s]=None
V=dict()
vu=set()
while F:
u=F.pop_smallest()
vu.add(u)
for vin G[u]:
if v not in vu:
if v in F and G[u][v]<F[v]:
F[v]=G[u][v] #poids de chaque sommet voisin
for n in F:
V[u]=dict({v:F[v]}) #dictionnaire à returner
for key,value in V.items():
if pere[value]==key and F[value] != float('inf'):
V[key][value]=F[value] #ajout de chaque sommet voisin de key existant
F.pop_smallest()
return V |
Partager