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
| import numpy as np
oo = np.inf #Définir l'infini
sommets = [0,1,2,3,4]
Adj = np.array([[0,8,2,1,oo],
[8,0,5,6,1],
[2,5,0,oo,3],
[1,6,oo,0,oo],
[oo,1,3,oo,0] ])
def plusCourt(T,I):
minimum = oo
indice = 0
for i in I:
if T[i] < minimum and T[i] > 0:
indice = i
minimum = T[i]
return indice
def dijkstra(Adj,s0):
n = len(Adj)
Dist = oo * np.ones(n)
Dist[s0] = 0
NonMarques = [k for k in range(n)]
Marques = [ ]
while len(Marques) < n:
i = plusCourt(Dist,NonMarques)
Marques.append(i)
NonMarques.remove(i)
for k in NonMarques:
if Dist[i] + Adj[i,k] < Dist[k]:
Dist[k] = Dist[i] + Adj[i,k]
return Dist |
