from metakernel import register_ipython_magics
register_ipython_magics()
L = [
[ (2,4), (1,10)], #0
[ (4,4) ], #1
[ (1,3), (3,12) ], #2
[ ], #3
[ (3,3) ] #4
]
M = [
[None, 10, 4, None, None],
[None,None,None,None, 4],
[None, 3, None, 12, None],
[None, None, None, None, None],
[None, None, None, 3, None]
]
def plus_proche(la, u) :
s, m = None, None
for v,p in la[u] :
if m == None or p < m :
s, m = v, p
return s, m
def prio(L, D) :
i_min, m = None, None
for i in range(len(L)) :
p = D[L[i]]
if m == None or ( p != None and p < m ) :
i_min, m = i, p
# Suppression
u = L[i_min]
L[i_min] = L[-1]
L.pop()
# Retour
return u
def relachement(D,P,a) :
u,p,v = a
if D[v] == None or D[u] + p < D[v] :
D[v] = D[u] + p
P[v]= u
return
def dijkstra(la, s) :
n = len(la)
# Structures
D = [None]*n
P = [None]*n
L = [ s for s in range(n) ]
# Initialisation
D[s] = 0
while len(L) > 0 :
u = prio(L, D)
for v,p in la[u] :
relachement(D,P,(u,p,v))
return (D,P)
def chemin(P,u) :
c = [u]
while P[c[-1]] != None :
c.append(P[c[-1]])
return list(reversed(c))
D,P = dijkstra(L,0)
D
[0, 7, 4, 14, 11]
chemin(P,4)
[0, 2, 1, 4]
chemin(P,2)
[0, 2]
def prio2(L, D, h, d ) :
i_min, m = None, None
for i in range(len(L)) :
p = D[L[i]]
if m == None or ( p != None and p + h(L[i],d) < m ) :
i_min, m = i, p+ h(L[i],d)
# Suppression
u = L[i_min]
L[i_min] = L[-1]
L.pop()
# Retour
return u
def astar(la, h, s, d) :
n = len(la)
# Structures
D = [None]*n
P = [None]*n
L = [ ]
in_L = [ False ] * n
# Initialisation
L.append(s)
D[s] = 0
in_L[s] = True
while len(L) > 0 :
u = prio2(L, D, h, d)
if u == d :
return ( D[d], P )
in_L[u] = False
for v,p in la[u] :
tmp = D[v]
relachement(D,P,(u,p,v))
if not in_L[v] and ( ( tmp == None and D[v] != None ) or ( D[v] != None and D[v] < tmp ) ) :
L.append(v)
in_L[v] = True
return
def h0 (x,y) :
return 0
def h1 (x,y) :
d = plus_proche(L,x)[1]
if d == None :
d = 10000
return d
def h2 (x,y) :
if x == 2 :
return 10000
else :
return 0
d, P = astar(L, h0, 0, 4)
d, chemin(P,4)
(11, [0, 2, 1, 4])
d, P = astar(L, h1, 0, 4)
d, chemin(P,4)
(11, [0, 2, 1, 4])
d, P = astar(L, h2, 0, 3)
d, chemin(P,3)
(17, [0, 1, 4, 3])