### dijksta

import numpy as np

def dijkstra(M,s):

""" M : matrice, s: sommet de départ"""

infini=M[0,0] #valeur des cases non définies

n=len(M[:,0]) # le nombre de sommets

A=[]

C=list(range(0,n))

distance=np.ones(n,dtype=type(infini))* infini

distance[s]=0 # on somme les poids

pred=np.ones(n,dtype=int)*s

while C!=[]:

C.sort(key=lambda i:distance[i])

a=C[0]

for c in C:

if distance[a]+ M[a,c] < distance[c]:

distance[c]=distance[a]+M[a,c]

pred[c]=a

A.append(a)

C.remove(a)

return s,pred,distance,infini

M=np.array([ [99,10,99,99, 6,99],\

[ 0,99,99,99,99,99],\

[99, 4,99,99, 3,99],\

[ 99, 1,99,99,3,99],\

[99, 0,99,99,99, 3],\

[ 2, 6,99,99, 5,99] ])

print(dijkstra(M,0))