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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| # -*- coding: utf-8 -*-
# Dijkstra
graphe = [[],[2,1,4,7],[1,1,5,1],[4,1,7,3,5,1],[1,7,3,1],[6,2,2,1,3,1],[5,2,7,3,8,1,9,4],[3,3,8,1,6,3],[6,1,7,1,9,2],[6,4,8,2],[2,1,3,1,11,3],[5,1,10,3]]
def recupere(Liste, sommet):
"""récupère l'indice dans la liste d'un sommet, s'il est présent"""
if len(Liste)>0:
for k in range(len(Liste)):
if Liste[k][0]== sommet:
return True, k
return False, -1
def mini(Liste):
""" renvoie l'indice du minimum dans la liste"""
minim = Liste[0][1]
indice = 0
for k in range(len(Liste)):
if minim> Liste[k][1]:
minim = Liste[k][1]
indice = k
return minim, indice
def Dijkstra(G, depart, arrivee):
solution =[]
optimal = [[depart, 0, []]]
atteint = []
nbtotal = len(G)
fini = False
while not fini:
sommet , distance, precedent = optimal[-1] #on prend le dernier sommet étudié dans la liste optimal
nb = len(graphe[sommet])//2 # C'est le nombre de sommets qu'on peut atteindre à partir de ce sommet
if nb>0:
for k in range(0, 2*nb, 2):
s = graphe[sommet][k] # on étudie le sommet s
test, indice = recupere(optimal, s)
if not test : # si le sommet n'est pas déjà dans optimal
test, indice = recupere(atteint, s)
if test : # on regarde s'il a été atteint déjà
if atteint[indice][1] > distance + graphe[sommet][k+1]:
atteint[indice][1] = distance + graphe[sommet][k+1] # on améliore le chemin
atteint[indice][2] = sommet # on réinitialise la façon de l'atteindre
else :
atteint.append([s, distance + graphe[sommet][k+1], sommet]) # on le rajoute dans les sommets atteints
#on s'intéresse au nouveau sommet de chemin minimal qu'on vient de trouver
minim, indice = mini(atteint)
info = atteint.pop(indice)#on le supprime des sommets atteints en récupérant les informatiosn le concernant
optimal.append(info) # on le rajoute aux sommets de chemin optimal
if info[0]==arrivee:
L = reconstruit_chemin(optimal,depart,arrivee)
fini = True
if len(atteint)==0:
fini = True
return L
def reconstruit_chemin(optimal, depart, arrivee):
sommet = arrivee
L=[arrivee]
while sommet!=depart:
test, indice = recupere(optimal, sommet)
L.append(optimal[indice][2])
sommet=optimal[indice][2]
L.reverse()
return L |
