Scribd
Importer
19 vues1 page

(S, A) Naive

Transféré par

bahaaeddinejafari
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
19 vues1 page

(S, A) Naive

Transféré par

bahaaeddinejafari
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

# Algorithme de Dijkstra

""" Réprésentation G = (S,A) plus la liste des poids """

def voisins(i,G,poids): # non orienté


A = G[1]
return [(sum(A[k])-i,poids[k]) for k in range(len(A)) if i in A[k]]

def trouveMin(Q,d):
p = 0 # p sera la position du sommet ayant la distance minimale
for i in range(1,len(Q)):
if d[Q[i]] < d[Q[p]] :
p = i
return Q.pop(p) # renvoyer le sommet Q[p] et le supprimer de Q

def dijkstra(G,poids,Sdeb,Sfin):
""" initialisation """
n = len(G[0]) # nombre de sommets
P = []
Q = [Sdeb]
d = [float('inf')] * n
d[Sdeb] = 0
pred = [None] * n

""" La recherche des chemins """


while Q :
sommet = trouveMin(Q,d)
if sommet == Sfin : break
P.append(sommet)
for v,p in voisins(sommet,G,poids) :
if v not in P and d[sommet] + p < d[v]: # Pb de complexité de not
in
d[v] = d[sommet] + p # mettre à jour sa distance
pred[v] = sommet # mettre à jour son prédecesseur
if v not in Q : Q.append(v) # Pb de complexité de not in

""" Déterminer le chemin de Sdeb à Sfin """


if pred[Sfin] is None : return 'Pas de chemin trouvé'
chemin = [Sfin]
sommet = Sfin
while sommet != Sdeb :
sommet = pred[sommet]
chemin.append(sommet)
chemin.reverse() # inverser le chemin
return (chemin, d[Sfin])

Vous aimerez peut-être aussi